Số lượng ước số của n

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 100 Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Viết chương trình nhập vào số nguyên \(n\) (\(n\leq 10^7\)). In ra số lượng ướ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ì \(4\) ước số: \(1\) \(2\) \(5\) \(10\)

Input

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

Output

  • In ra số lượng ước số của \(n\).

Example

Test 1

Input 
10
Output 
4

Test 2

Input 
36
Output 
9

Bình luận


  • 6
    tk22dangminhduc    12:06 p.m. 2 Tháng 8, 2023

    SOLUTION:

    Bài này có 2 phương pháp giải

    Cách 1:
    Duyệt for từ 1 đến sqrt(n) (căn bậc 2), nếu số đó chia hết cho n (hay còn gọi là ước) của n thì +2, nhưng nếu n là một số chính phương thì khi duyệt đến căn bậc 2 của n, chúng ta chỉ +1.

    Cách 2:
    Phuơng pháp này chỉ áp dụng với số > 1
    1: Phân tích n sang thừa số nguyên tố
    2: lấy các số mủ của các thừa số nguyên tố +1
    3: tính tích của dãy số vừa tìm được
    vd : 20 = \(2^2\) * \(5^1\)
    -dãy số mủ số sau khi +1 là (3; 2)
    -tính tích = 3 * 2 = 6
    Vậy kq=6
    hãy kiểm chứng Ư(20) = {1; 2; 4; 5; 10; 20}, kq = 6
    => Dù n là 1 số nguyên tố thì cách này vẫn đúng!

    • 11 bình luận nữa