Problema
Un número es abundante cuando sus divisores propios (todos sus divisores excepto él mismo) suman más que él. El 12 es el menor: 1 + 2 + 3 + 4 + 6 = 16. Algunos números se pueden escribir como suma de dos números abundantes (se puede usar el mismo dos veces, como en 24 = 12 + 12) y otros no. Suma todos los enteros positivos del 1 a limit que no se pueden escribir así.
Implementa non_abundant_sums(limit).
Calcula de una vez las sumas de divisores de todos los números con una criba, haz la lista de los números abundantes y marca cada suma de dos de ellos que no supere el límite.
Entrada
limit: el mayor número que hay que comprobar.
Salida
Devuelve la suma de todos los n con 1 ≤ n ≤ limit que no son suma de dos números abundantes.
Restricciones
1 ≤ limit ≤ 10,000
Ejemplos
Entrada:
limit = 23
Salida esperada:
expected = 276
Entrada:
long long limit = 23;
Salida esperada:
long long expected = 276;
Entrada:
long limit = 23;
Salida esperada:
long expected = 276;
Explicación
Ningún par de números abundantes suma 23 o menos, así que todos los números cuentan: 1 + 2 + ... + 23 = 276.
Entrada:
limit = 30
Salida esperada:
expected = 411
Entrada:
long long limit = 30;
Salida esperada:
long long expected = 411;
Entrada:
long limit = 30;
Salida esperada:
long expected = 411;
Explicación
Quedan fuera 24 = 12 + 12 y 30 = 12 + 18, así que la respuesta es 465 − 24 − 30 = 411.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Para cada i, suma i a la suma de divisores de 2i, 3i, 4i, ...
Pista 2
Reúne los números abundantes en orden creciente.
Pista 3
Para cada pareja a ≤ b, detén el bucle interior en cuanto a + b supere el límite.
Complejidad esperada
tiempo O(limit log limit + A²) para A números abundantes, espacio extra O(limit)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.