Criba de Eratóstenes

Problema:

Dado un natural n, escriba una función que busque todos los primos menores o iguales a n.

Ejemplos:

Entrada: n = 10; Salida: 2 3 5 7

Entrada n = 23; Salida: 2 3 5 7 11 13 17 19 23

Idea del algoritmo:

1. Se crea un arreglo de tipo booleano de tamaño n+1.
2. Empezando por el número 2, se “tachan” todas las posiciones que sean múltiplos de 2.
3. Esto se realiza asignando el valor 0 a dichas posiciones.
4. Luego, partiendo de la siguiente posición (p) que no tenga asignado valor 0, se “tachan” todas las posiciones que sean múltiplos de p. Este paso se realiza mientras 𝑝≤n.

Código:

Disponible en Criba de Eratóstenes

Ejemplo de uso:

Disponible en ejemplo Criba de Eratóstenes

Explicación animada:

En el artículo de Wikipedia: Criba de Eratóstenes y Criba de Euler

Complejidad:

La complejidad de la Criba de Eratóstenes: O(N * log(log N)), una complejidad muy cercana -apenas superior- a la lineal.

Problemas en sitios jueces:

omegaUp: Números Primos

Spoj: PRIME1 - Prime Generator