La criba de Eratóstenes

La criba de Eratóstenes es el procedimiento más antiguo que se conoce para obtener todos los números primos menores que un límite dado, y sigue siendo uno de los más rápidos. No comprueba los números uno a uno para ver si son primos. Hace lo contrario: escribe todos los números en fila y va tachando los que seguro que no lo son, los múltiplos de los primos que ya ha encontrado. Lo que sobrevive al final son exactamente los primos. La idea es tan sencilla que cabe en una tabla de cien casillas y se enseña en la escuela, pero detrás hay dos observaciones que la hacen eficaz y que conviene entender: dónde se empieza a tachar y dónde se puede parar.

El nombre viene de Eratóstenes de Cirene, el erudito del siglo III a. C. que dirigió la Biblioteca de Alejandría y que es más recordado por haber medido la circunferencia de la Tierra. No se conserva ningún texto suyo que describa el método. Lo atribuye a él Nicómaco de Gerasa, que hacia el año 100 lo explica en su Introducción a la aritmética y lo llama «criba» (en griego, kóskinon), porque los números compuestos se van colando por los agujeros y los primos quedan retenidos. La descripción de Nicómaco es la de siempre: se escriben los impares a partir del 3, se toma el primero, se salta de tres en tres marcando, se toma el siguiente que no esté marcado, y así sucesivamente.

El procedimiento, tal como se aplica hoy, es este. Se escriben los números del 2 al límite $N$. El primero, el 2, es primo, y se tachan todos sus múltiplos. El primer número que queda sin tachar después del 2 es el 3, que tiene que ser primo, porque si fuera compuesto tendría un divisor menor y ya habría caído. Se tachan sus múltiplos. El siguiente sin tachar es el 5, y se repite. Cada vez que se busca el siguiente número vivo, ese número es primo por la misma razón: nadie más pequeño lo ha tachado, así que no tiene divisores más pequeños que 1.

La primera observación que ahorra trabajo es que los múltiplos de un primo $p$ se empiezan a tachar en $p^2$ y no en $2p$. Todos los múltiplos menores, $2p$, $3p$, …, $(p-1)p$, tienen un factor menor que $p$, así que ya los tachó un primo anterior. Cuando llega el turno del 7, el 14 cayó con el 2, el 21 con el 3 y el 35 con el 5; el primer múltiplo de 7 que todavía está vivo es 49. En la figura se ve que, a medida que los primos crecen, cada ronda tacha menos números nuevos y más dispersos.

La segunda observación es la consecuencia directa de la primera: si el siguiente primo $p$ cumple que $p^2 > N$, ya no queda nada que tachar, y todo lo que sigue sin marcar es primo. Por eso para obtener los primos hasta 100 basta con cribar con 2, 3, 5 y 7, porque $11^2 = 121$. Es la misma razón por la que, para saber si un número concreto es primo, basta con probar divisores hasta su raíz cuadrada: un número compuesto $n = a \cdot b$ tiene siempre un factor menor o igual que $\sqrt{n}$. Hasta 100 quedan 25 primos, y hasta 200, 46.

El coste de la criba se puede contar con precisión. Para cada primo $p$ hasta $\sqrt{N}$, el método da unos $N/p$ pasos tachando. La suma de $1/p$ sobre los primos crece muy despacio, como el logaritmo del logaritmo, de modo que el total es del orden de $N \log \log N$ operaciones. Para un millón, $\log \log N$ vale menos de 3: la criba hace poco más de dos pasadas completas por la tabla. Comparado con comprobar cada número por separado dividiendo por los primos anteriores, la diferencia es enorme, porque la criba nunca divide: solo suma $p$ para saltar al siguiente múltiplo, y esa operación la hace un ordenador en un instante. En notación de orden de complejidad, la criba es casi lineal.

El inconveniente es la memoria. La criba necesita tener la tabla entera a la vista, un bit por número. Para los primos hasta mil millones son unos 125 megabytes, que hoy no es nada, pero para rangos mayores la tabla no cabe. La solución habitual es la criba segmentada: se criban primero los primos hasta $\sqrt{N}$, que son pocos, y con ellos se procesa el rango completo por tramos que caben en la memoria rápida del procesador, uno tras otro. Así se generan tablas de primos de billones de números sin guardar nunca más que un trozo. También se ahorra la mitad del trabajo dejando fuera los pares desde el principio, que es exactamente lo que hacía Nicómaco al escribir solo los impares.

A lo largo del siglo XX se buscaron cribas que hicieran un número de operaciones estrictamente proporcional a $N$, sin el factor $\log \log N$. La idea es tachar cada número compuesto una sola vez, por su factor primo más pequeño, en lugar de dejar que lo tachen todos sus factores. En 1987 Paul Pritchard ordenó esas variantes en un árbol genealógico y mostró cómo se derivan unas de otras. En la práctica la ganancia es pequeña, porque $\log \log N$ es casi una constante y las cribas lineales hacen más trabajo por paso, así que la versión clásica y la segmentada siguen siendo las más usadas.

Hay una trampa conocida alrededor del nombre. En los cursos de programación funcional se ha enseñado durante años una «criba» de una sola línea que toma el primer número de una lista, lo declara primo y filtra de la lista todos los que son divisibles por él, y repite con lo que queda. Parece la criba, pero no lo es. En 2009 Melissa O’Neill mostró que ese programa comprueba cada número dividiéndolo por todos los primos anteriores, uno a uno, hasta que alguno lo divide o se acaban: es división por tentativa disfrazada, y resulta más lenta que la criba verdadera por un factor que crece con el tamaño del problema. La diferencia está en el mecanismo. La criba real no pregunta a un número si es divisible; llega a él saltando desde su factor primo. O’Neill propuso una versión funcional que respeta esa idea y que es tan eficiente como la de la tabla.

Los números primos importan porque son los ladrillos de todos los demás: según el teorema fundamental de la aritmética, cada entero mayor que 1 se escribe como producto de primos de una única manera. De ahí salen sus usos modernos, desde la criptografía de clave pública, que confía en lo difícil que es deshacer ese producto cuando los factores son enormes, hasta las tablas hash, que usan tamaños primos para repartir mejor las claves. Para encontrar un primo de trescientas cifras no se usa la criba, sino pruebas de primalidad que examinan un solo número. Pero para obtener todos los primos de un intervalo, que es lo que hace falta para contar cuántos hay y estudiar cómo se reparten, la criba sigue siendo la herramienta. Lo que muestra esa cuenta es el asunto del teorema de los números primos.