Problema
Devuelve todos los números primos desde 2 hasta limit. Un primo es un entero mayor que 1 divisible solo por 1 y por sí mismo. Usa la idea de la criba: conserva el siguiente número no marcado y marca como compuestos sus múltiplos mayores. Lista los resultados en orden ascendente.
Implementa sieve_primes(limit).
Entrada
limit: El número más grande que puede incluirse.
Salida
Devuelve los primos en orden ascendente, o una lista vacía si no existe ninguno.
Restricciones
0 ≤ limit ≤ 100,000. El límite superior es inclusivo. Las pruebas de salida verifican los resultados, no el algoritmo exacto utilizado.
Ejemplos
Entrada:
limit = 12
Salida esperada:
expected = [2, 3, 5, 7, 11]Entrada:
long long limit = 12;
Salida esperada:
std::vector<long long> expected = {2, 3, 5, 7, 11};Entrada:
long limit = 12;
Salida esperada:
long[] expected = new long[] {2, 3, 5, 7, 11};Explicación
Marca los múltiplos de 2 y 3 como compuestos. Los valores restantes hasta 12 son 2, 3, 5, 7 y 11.
Entrada:
limit = 1
Salida esperada:
expected = []Entrada:
long long limit = 1;
Salida esperada:
std::vector<long long> expected = {};Entrada:
long limit = 1;
Salida esperada:
long[] expected = new long[] {};Explicación
Los números primos comienzan en 2, más allá de este límite.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Marca los compuestos empezando desde cada candidato primo no marcado y continúa hasta el límite.
Pista 2
Solo los números que sigan sin marcar al final son primos.
Pista 3
Deja de marcar múltiplos cuando el cuadrado del candidato supere el límite.
Complejidad esperada
tiempo O(n log log n), espacio extra O(n)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.