Đề bài
The proper divisors of n are the positive divisors other than n itself. For 12 they are 1, 2, 3, 4 and 6. Their sum (sometimes called the aliquot sum) tells whether a number is perfect, abundant or deficient. Divisors come in pairs d and n / d, so you only need to try values of d up to the square root of n.
Implement sum_of_proper_divisors(n).
Input
n: A positive integer.
Output
Return the sum of all positive divisors of n that are less than n. For n = 1 there are none, so return 0.
Ràng buộc
1 ≤ n ≤ 10^12
Ví dụ
Đầu vào:
n = 12
Kết quả mong đợi:
expected = 16
Đầu vào:
long long n = 12;
Kết quả mong đợi:
long long expected = 16;
Đầu vào:
long n = 12;
Kết quả mong đợi:
long expected = 16;
Giải thích
1 + 2 + 3 + 4 + 6 = 16.
Đầu vào:
n = 28
Kết quả mong đợi:
expected = 28
Đầu vào:
long long n = 28;
Kết quả mong đợi:
long long expected = 28;
Đầu vào:
long n = 28;
Kết quả mong đợi:
long expected = 28;
Giải thích
1 + 2 + 4 + 7 + 14 = 28, so 28 is a perfect number.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
If d divides n, then n / d divides n too.
Gợi ý 2
Only try d up to the square root of n, adding both members of each pair.
Gợi ý 3
Leave n itself out, and add the square root only once when n is a perfect square.
Độ phức tạp mong đợi
O(sqrt n) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.