Все задачи
Легко Решено: 0 Процент решений: 0%

Сумма собственных делителей

Сложите все делители числа n, меньшие самого n.

Чему вы научитесь

  • Находить делители парами
  • Останавливать цикл на квадратном корне
  • Не учитывать делитель, равный квадратному корню, дважды

Условие

Собственные делители числа 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

Примеры

Пример 1
Ввод:
n = 12

Ожидаемый вывод:
expected = 16
Ввод:
long long n = 12;

Ожидаемый вывод:
long long expected = 16;
Ввод:
long n = 12;

Ожидаемый вывод:
long expected = 16;

Пояснение

1 + 2 + 3 + 4 + 6 = 16.

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.