La criba de Eratostenes

La criba de Eratostenes es un algoritmo para hallar todos los números primos menores a un número dado. Recordamos que un número primo es aquel que solo se puede dividir por sí mismo y por la unidad.

El algoritmo consiste en crear una tabla con todos los números e ir eliminando los que sean múltiplos de otro, o dicho de otro modo, los que tengan más divisores que ellos mismos y la unidad. La tabla comenzará en el 2 y finalizará en el número que marquemos como límite para hallar números primos. El 1 no se considera número primo, de ahí que se comience por el número 2.

Pasos del algoritmo

• Marcamos el primer número primo de la lista y tachamos a continuación todos sus múltiplos  en la tabla.
• Escogemos el siguiente número y comprobamos si su cuadrado es mayor o menor que el último número de la tabla. Si es mayor se termina el algoritmo, si es menor tenemos que repetir el proceso anterior indefinidamente hasta que se cumpla la condición.
• Los números primos serán los números señalados para hacer los recorridos del algoritmo más todos los números que queden sin marcar.

Vamos a hallar todos los números primos existentes hasta el 100 mediante la criba de Eratostenes.

1.- Creamos una tabla con todos los números entre el 2 y el número límite, en este caso el 100, y marcamos el 2 como primer número primo de la lista.

2.- Marcamos todos los múltiplos de 2 en la tabla. Los números pares de la tabla son divisibles por 2 por lo que este primer paso es sencillo.

3.- El primer número no marcado es el 3. Comprobamos si el cuadrado de 3 es mayor que el último número de la tabla, el 100. Como el cuadrado de 3 es 9 debemos continuar el proceso así que señalamos el número 3 como siguiente número primo.

4.- Marcamos todos los múltiplos de 3 en la tabla. Recuerda cuando un número es divisible por 3.

5.- Repetimos la comprobación para ver si hemos terminado. El primer número sin marcar es 5, su cuadrado es 25  por lo que es menor que 100 así que debemos continuar. Señalamos el 5.

6.- Marcamos todos los múltiplos de 5 que no estén ya marcados.

7.- Comprobamos. El cuadrado de 7 es 49, que es menor que 100 así que marcamos el 7 como siguiente número primo.

8.- Marcamos todos los múltiplos de 7 que no estén ya marcados.

9.- Comprobamos. El primer número de la lista es el 11, el cuadrado de 11 es 121 así que como supera a 100 damos por finalizado el cribado de Eratostenes.

Los números que han quedado sin marcar y los números que hemos señalado para iterar el algoritmo (2, 3, 5, 7) forman el total de números primos menores que 100.

Los números primos entre el 1 y el 100 son:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Los rojos son por haber sido los señalados en las iteraciones del algoritmo y el resto de números por no haber sido marcados.