Problema
Un número primo es un entero mayor que 1 que solo es divisible por 1 y por sí mismo. Suma todos los primos estrictamente menores que limit. El propio límite se excluye incluso si es primo.
Implementa prime_sum(limit).
Entrada
limit: El límite superior exclusivo.
Salida
Devuelve la suma de los primos elegibles, o 0 si no existe ninguno.
Restricciones
0 ≤ limit ≤ 2,000,000. Devuelve la suma usando un entero con signo de 64 bits.
Ejemplos
Entrada:
limit = 12
Salida esperada:
expected = 28Entrada:
long long limit = 12;
Salida esperada:
long long expected = 28;Entrada:
long limit = 12;
Salida esperada:
long expected = 28;Explicación
Los primos menores que 12 son 2, 3, 5, 7 y 11; su suma es 28.
Entrada:
limit = 2
Salida esperada:
expected = 0Entrada:
long long limit = 2;
Salida esperada:
long long expected = 0;Entrada:
long limit = 2;
Salida esperada:
long expected = 0;Explicación
No hay primos estrictamente menores que 2.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
El coste principal es encontrar primos eficientemente; comprobar divisibilidad de forma ingenua para cada número será demasiado lento.
Pista 2
Usa un enfoque tipo criba para marcar compuestos y luego sumar los números que queden sin marcar y por debajo del límite.
Pista 3
Recuerda que el propio límite se excluye, incluso cuando es primo, y los límites pequeños pueden no aportar nada.
Complejidad esperada
tiempo O(limit log log limit), espacio extra O(limit)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.