Tamiz de Eratóstenes

Es posible encontrar todos los números primos menores que n mucho más rápido que haciendo una verificación de primalidad para cada número desde 2 hasta n. Podemos cambiar el enfoque y, en lugar de revisar cada número para ver si es primo, eliminar proactivamente de la lista todos los que ya sabemos que no van a ser primos.

Para empezar, podemos marcar todos los números desde 2 hasta n como “posiblemente primos”. Luego, eliminamos de esa lista todos los múltiplos de 2 y marcamos el 2 como “definitivamente primo”. Después, removemos todos los múltiplos de 3 y marcamos el 3 como “definitivamente primo”. Saltamos el 4 porque ya lo quitamos de la lista de posibles primos cuando procesamos el 2. El siguiente número a considerar es el 5, y también eliminaremos todos sus múltiplos. El 6 se omite porque ya fue marcado como no primo durante el procesamiento del 2. Podemos continuar este proceso hasta llegar a n.

Simulación del tamiz de Eratóstenes. Haz clic sobre los números y trata de habilitar todos los primos, mientras deshabilitas los demás.

Propiedades interesantes y optimizaciones del algoritmo

Una gran consecuencia de eliminar todos los múltiplos de un número primo p de la lista de “posiblemente primos”, empezando desde el más pequeño (2) e incrementando gradualmente p, es que en lugar de procesar todos los múltiplos 2·p, 3·p, 4·p, 5·p..., podemos comenzar directamente en p·p. Puesto que los múltiplos de p como 2·p, 3·p, 4·p, 5·p ya han sido eliminados cuando procesamos los números 2, 3, 5…, el primer número que aún no ha sido tocado es p·p.

Por lo tanto, cuando empezamos a procesar p=3, podemos arrancar directamente desde 9, porque el 6 ya fue eliminado en la fase en que revisamos el 2. De modo similar, cuando procesamos el p=5, podemos empezar directamente con 25, pues el 10 (10 = 2·5) fue eliminado cuando se procesó el 2, el 15 (15 = 3·5) se eliminó al procesar el 3 y, finalmente, el 20 (20 = 4·5) se retiró cuando procesamos el 2.

prime = [True] * n                    # prime[i] = True => i se considera número primo
prime[0] = prime[1] = False           # 0 y 1 no son primos

for i in range(2, n):                 # Bucle desde 2 hasta n
    if prime[i]:                      # si i es primo => marcar todos los múltiplos de i como no primos
        for j in range(i * i, n, i):  # iniciamos en i * i, pues los múltiplos menores ya fueron marcados antes
            prime[j] = False

Sieve of Eratosthenes to find all the prime numbers smaller than n.

Simulemos este proceso para n=100:

prime = [False, False, True, True, ..., True] de tamaño 100

i = 2 ⇒ prime[2] = True ⇒ para j en 4, 6, 8, ... 100 marcar prime[j]=False

i = 3 ⇒ prime[3] = True ⇒ para j en 9, 12, ... 100 marcar prime[j]=False

i = 4 ⇒ prime[4] = False

i = 5 ⇒ prime[5] = True ⇒ para j en 25, 30, ... 100 marcar prime[j]=False

i = 6 ⇒ prime[6] = False

i = 7 ⇒ prime[7] = True ⇒ para j en 49, 56, ... 100 marcar prime[j]=False

i = 8 ⇒ prime[8] = False

i = 9 ⇒ prime[9] = False

i = 10 ⇒ prime[10] = False

i = 11 ⇒ prime[11] = True ⇒ para j en [vacío] marcar prime[j]=False

Aquí podemos detenernos porque i * i ya es mayor que n. Por lo tanto, no marcaremos más números como False desde este punto en adelante. Luego, podemos recorrer la lista y mostrar todos los números primos menores que 100.

Este método es significativamente más rápido y realiza operaciones. ¡Es una mejora enorme! Llevar a cabo operaciones en lugar de marca una gran diferencia. Volviendo al ejemplo del algoritmo que requería 10 años (3650 días) si hacía n operaciones, y 2 meses (61 días) si hacía operaciones, con se necesitarían menos de 4 días.

Otra optimización mencionada en la simulación es hacer que el bucle de i vaya desde 2 hasta , ya que el bucle interno comienza en i·i y, por lo tanto, para todos los números mayores que la raíz cuadrada de n, no marcaremos más valores como prime[j] = False en el bucle interno (el límite superior del bucle interno es n).

Entrada

La primera línea de la entrada contiene un único entero n (2 ≤ n ≤ ).

Salida

El programa debe imprimir todos los números primos menores o iguales que n.

Ejemplos

Input	Output
8	2 3 5 7
17	2 3 5 7 11 13 17
19	2 3 5 7 11 13 17 19

Propiedades interesantes y optimizaciones del algoritmo

Entrada

Salida

Ejemplos

Constraints

To check your solution you need to sign in

Sign in to continue