Ước số của n

View as PDF



Authors:
Problem types
Points: 100 Time limit: 1.0s Memory limit: 640M Input: stdin Output: stdout

Viết chương trình nhập vào số nguyên \(n\) (\(n\leq 10^7\)). In ra tất cả các ước số của \(n\). (Ước số của \(n\) là các số nguyên mà \(n\) chia hết)

Ví dụ: \(n=10\) thì in ra các số: \(1\) \(2\) \(5\) \(10\)

Input

  • Một số nguyên dương \(n\).

Output

  • In ra các ước số của \(n\).

Example

Test 2

Input
10
Output
1 2 5 10

Test 2

Input
36
Output
1 2 3 4 6 9 12 18 36

Comments


  • 1
    kay    9:16 p.m. 25 mar, 2024

    code python:
    n = int(input())
    for i in range(1,n+1):
    if n%i==0:
    print(i)


    • 2
      dxuloc    11:15 a.m. 6 feb, 2024

      test cuối lỗi à


      • 2
        khoinguyentl2023    9:50 a.m. 11 apr, 2023

        tang thoi gian cho python di a


        • -1
          tranminhkhoi    6:22 p.m. 29 oct, 2020

          help mình với

          4 replies

          • 2
            SPyofgame    9:18 p.m. 7 jun, 2020

            Spoiler Alert

            Hint 1

            Gọi D(x) là tập hợp các ước của x

            **D(x) = {y ∈ D(x) | y ≤ k} Λ {z ∈ D(x) | z > k} **

            Hint 2

            Đặt k tới đâu, mình chỉ cần duyệt trong O(k) là xong

            Hint 3

            n = a * b và (a < b), theo bđt Cauchy thì a ≤ √nb > √n

            Duyệt tới k = √n là tối ưu nhất

            Reference

            C++
            int main()
            {
                /// Nhan gia tri
                int n = readInt();
            
                vi lower; /// {y ∈ D(x) | y ≤ k}
                vi upper; /// {z ∈ D(x) | z > k}
            
                /// Tim cac uoc
                int sqrtn = sqrt(n);
                for (int i = 1; i <= sqrtn; ++i)
                    if (n % i == 0)
                        lower.push_back(i),
                        upper.push_back(n / i);
            
                /// Tach phan chung khi (n) la so chinh phuong
                if (lower.back() == upper.back()) upper.pop_back();
                reverse(all(upper));
            
                /// In ket qua
                for (int x : lower) cout << x << ' ';
                for (int x : upper) cout << x << ' ';
                return 0;
            }