Es un método para hallar números primos descrita por Eratóstenes de Cirene alrededor del siglo III ane, y que Nicómaco de Gerasa recoge en su libro, del siglo I, Arithmetike Eisagoge (introducción a la aritmética).
El método es simple, consiste en rellenar una tabla (matriz) de números naturales sucesivos empezando por el 1 hasta donde queramos llegar.
De la tabla se van extrayendo o quitando todos los múltiplos de 2, el siguiente número que aparece es el 3 (primo), se vuelve a repetir la acción, se quitan todos los múltiplos de tres, el siguiente número es el 5 (primo), se vuelve a repetir la acción, y así sucesivamente para el resto de números de la tabla.
Todos los números que quedan son primos, incluido el 1 que en aquella época sí se le consideraba primo.
Algunas cosas antes de comenzar:
- Sí lo realizamos manualmente sólo nos sirve para identificar números primos pequeños.
- Al utilizar un ordenador (de los de andar por casa) nos encontramos con varias limitaciones:
- La memoria.
- Asignación en el tamaño de la tabla, condicionada actualmente (2.012) por el máximo valor de un entero y dependiente del lenguaje de programación / sistema que utilicemos.
De todas formas hay curiosidades al utilizar este método, algunas de ellas nos permiten tomar atajos e ir más rápido. Creemos una tabla de n filas y 6 columnas, ¿por qué?, muy fácil:
- Todos los pares son divisibles ente dos, aunque también lo sean por otros números y las columnas 2, 4 y 6 están llenas de pares.
- La columna 3 salvo el 3 son todos múltiplos de 3.
- Todos los múltiplos del siguiente nº no retirado (5) también se descartan.
- Todos los múltiplos del siguiente nº no retirado (7) también se descartan.
- Todos los múltiplos del siguiente nº no retirado (11) también se descartan.
- Y así sucesivamente…
Esto nos ayuda a evaluar que sólo debemos tomar las columnas 1 y 5, y los primos de la primera fila. Valorad cómo se están comportando las líneas diagonales roja y amarilla, también la utilización de otra cantidad de columnas, jugar un poco.
Aquí un ejemplo computacional. Observad que la segunda opción introduce el límite de los números tratados a: 
, es una condición que se adoptó posteriormente a las indicaciones de Eratóstenes.
