Criba de Eratóstenes
Se forma una tabla con todos los números naturales comprendidos entre 2 y n, y se van tachando los números que no son primos de la siguiente manera: Comenzando por el 2, se tachan todos sus múltiplos; comenzando de nuevo, cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos, así sucesivamente.
El proceso termina cuando el cuadrado del siguiente número confirmado como primo es mayor que n. Determinemos, mediante el siguiente ejemplo, el proceso para determinar la lista de los números primos menores de 20.
Un refinamiento de la criba consiste en tachar los múltiplos del k-ésimo número primo pk, comenzando por pk2 pues en los anteriores pasos se habían tachado los múltiplos de pk correspondientes a todos los anteriores números primos, esto es, 2pk, 3pk, 5pk,…, hasta (pk-1)pk.
[1] Otro refinamiento consiste en generar una lista solo con números impares (pues los números pares distintos de 2 se sabe que no son primos), e ir tachando los múltiplos de los números primos mediante incrementos de 2p, es decir, los múltiplos impares (2k+1)p de cada primo p. Esto aparece en el algoritmo original.
Salida: El conjunto de números primos anteriores a
La función zeta de Riemann se representa como Multiplicando ambos miembros por
se obtiene una nueva serie, y restando esta nueva serie a la serie original miembro a miembro y término a término, se eliminan todos los términos cuyas bases son múltiplos de 2 — En la criba de Eratóstenes se tachan —.
, se eliminan todos los términos cuyas bases son múltiplos de 3: Puede comprobarse que la parte de la derecha se está cribando, de manera que repitiendo este proceso indefinidamente: se obtiene un producto sobre todos los números primos p, que puede escribirse de forma simplificada como:
