Con este procedimiento hayaremos los números primos inferiores a un número.
Eratóstenes de Cirene (276-194 A.C.) fue un sabio griego que vivió hace unos dos mil doscientos años y que inventó un procedimiento para encontrar los números primos inferiores a n (aunque sirve para cualquier número dado).
Es simplemente un cuadrado donde aparecen los n primeros números y se van tachando los números que no son primos:
PROCEDIMIENTO
1.Se escriben todos los números en orden hasta n
2.Se tachan los múltiplos de 2 {4,6,8,10,12,14,16….} (En el dibujo no se tacha el 2 pero ya lo incluye como primo)
3.Buscamos el siguiente número sin tachar (en este caso el 3)
4.Tachamos los múltiplos de ese número
5.Mientras se pueda tachar volvemos al paso 3
Los números que quedan sin tachar son los números primos hasta n. En el caso del dibujo los números primos hasta 120.
Este un método práctico sencillo para obtener los n primeros números primos. Aunque requiere de almacenar los números, con posibles optimizaciones como eliminar los números pares, múltiplos de 3 o múltiplos de 5.
Con la subcriba de un único primo obtenemos todos los primos hasta el siguiente primo al cuadrado, por eso realizamos pi(sqrt(n)) sub-cribas, donde pi(x) es la función que cuenta los números primos hasta x.