Problema
Los divisores propios de n son sus divisores positivos distintos del propio n. Para 12 son 1, 2, 3, 4 y 6. Su suma (a veces llamada suma alícuota) indica si un número es perfecto, abundante o deficiente. Los divisores van en parejas d y n / d, así que basta con probar valores de d hasta la raíz cuadrada de n.
Implementa sum_of_proper_divisors(n).
Entrada
n: un entero positivo.
Salida
Devuelve la suma de todos los divisores positivos de n que son menores que n. Para n = 1 no hay ninguno, así que devuelve 0.
Restricciones
1 ≤ n ≤ 10^12
Ejemplos
Entrada:
n = 12
Salida esperada:
expected = 16
Entrada:
long long n = 12;
Salida esperada:
long long expected = 16;
Entrada:
long n = 12;
Salida esperada:
long expected = 16;
Explicación
1 + 2 + 3 + 4 + 6 = 16.
Entrada:
n = 28
Salida esperada:
expected = 28
Entrada:
long long n = 28;
Salida esperada:
long long expected = 28;
Entrada:
long n = 28;
Salida esperada:
long expected = 28;
Explicación
1 + 2 + 4 + 7 + 14 = 28, así que 28 es un número perfecto.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Si d divide a n, entonces n / d también divide a n.
Pista 2
Prueba d solo hasta la raíz cuadrada de n y suma los dos miembros de cada pareja.
Pista 3
No incluyas el propio n, y suma la raíz cuadrada una sola vez cuando n sea un cuadrado perfecto.
Complejidad esperada
tiempo O(sqrt n), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.