Собственные делители числа n - это все его положительные делители, кроме самого n. Для 12 это 1, 2, 3, 4 и 6. По их сумме (её иногда называют аликвотной суммой) можно понять, является ли число совершенным, избыточным или недостаточным. Делители идут парами d и n / d, поэтому достаточно перебирать d до квадратного корня из n.
Реализуйте sum_of_proper_divisors(n).
Входные данные
n: положительное целое число.
Выходные данные
Верните сумму всех положительных делителей n, меньших n. Для n = 1 таких делителей нет, поэтому верните 0.
Ограничения
1 ≤ n ≤ 10^12
Примеры
Ввод:
n = 12
Ожидаемый вывод:
expected = 16
Ввод:
long long n = 12;
Ожидаемый вывод:
long long expected = 16;
Ввод:
long n = 12;
Ожидаемый вывод:
long expected = 16;
Пояснение
1 + 2 + 3 + 4 + 6 = 16.
Ввод:
n = 28
Ожидаемый вывод:
expected = 28
Ввод:
long long n = 28;
Ожидаемый вывод:
long long expected = 28;
Ввод:
long n = 28;
Ожидаемый вывод:
long expected = 28;
Пояснение
1 + 2 + 4 + 7 + 14 = 28, значит, 28 - совершенное число.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Если d делит n, то и n / d делит n.
Подсказка 2
Перебирайте d только до квадратного корня из n и прибавляйте оба числа из каждой пары.
Подсказка 3
Не учитывайте само n, а квадратный корень прибавляйте только один раз, если n - полный квадрат.
Ожидаемая сложность
время O(sqrt n), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.