Tome un número entero positivo x. ¿Cómo puede encontrar todos los números primos que no superan x? Hay un método llamado criba de Eratóstenes, cuya historia se remonta a la antigua Grecia. Los pasos de la criba de Eratóstenes son los siguientes:
- En primer lugar, enumere todos los números enteros del 2 al x, y conserve el 2 y elimine todos los múltiplos de 2.
- En la lista restante, el siguiente número primo después del 2 es el 3; conserve el 3 y elimine todos los múltiplos de 3.
- En la lista restante, el siguiente número primo después del 3 es el 5; conserve el 5 y elimine todos los múltiplos de 5.
Y así sucesivamente. En el último paso, en la lista restante del paso anterior, conserve el número primo más cercano que no supere x y elimine todos sus múltiplos. De esta manera, la lista restante será todos los números primos que no superan x.
Este enfoque se basa en el hecho de que, si a no es un número primo, debe tener un factor que no supere √a.
Se puede usar la criba de Eratóstenes para elaborar tablas de números primos de manera más sencilla. Si se encuentra con un número entero positivo no muy grande (por ejemplo, no más de 10000) y no tiene una tabla de números primos disponible, ¿cómo puede determinar rápidamente si es un número primo? En realidad, solo tiene que probar todos los números primos que no superen √a para dividir a por ellos.