¿Qué es la Criba de Eratóstenes?

La criba de Eratóstenes (*) es un algoritmo que permite hallar todos los números primos menores que un número natural dado de valor = n.

La mejor forma de entender el procedimiento propuesto por el matemático griego es ingresando a la página de la referencia, donde se incluye una demostración dinámica del método.

De todos modos, el siguiente es el razonamiento que soporta el procedimiento:

Se forma una tabla con todos los números naturales comprendidos entre 2 y "n".

Se van tachando los números que no son primos de la siguiente manera:

1) Comenzando por el 2, se tachan todos sus múltiplos, es decir, todos los números pares.

2) En una segunda ronda, cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo (en esta ronda será el 3), y se procede a tachar todos sus múltiplos.

3) Se repite el procedimiento tantas veces como sea necesario (en la la tercera ronda se partirá del 7) hasta que el número primo de partida sea igual o superior al valor "n".

4) En la criba quedarán sin tachar todos los números primos menores a "n".

(*) Eratóstenes de Cirene fue un matemático, astrónomo y geógrafo griego de origen cirenaico. Concibió por primera vez la geografía como una disciplina sistemática, desarrollando una terminología que todavía se usa en la actualidad