La criba de Eratóstenes

El algoritmo: tachar los no-primos

La criba de Eratóstenes es un algoritmo del siglo III a.C. para encontrar todos los primos hasta un límite $N$. La idea es simple: empezar con la lista $2, 3, 4, \ldots, N$ y, a partir de cada primo encontrado, tachar todos sus múltiplos mayores que él.

Pasos: (1) Escribe los enteros de $2$ a $N$. (2) El primer número no tachado es $2$; táchalo de primo y testa todos sus múltiplos: $4, 6, 8, \ldots$ (3) El siguiente no tachado es $3$; ídem con $6, 9, 12, \ldots$ (4) El siguiente no tachado es $5$; táchalo y sus múltiplos. Continúa. (5) Cuando llegas a un número $p > \sqrt{N}$, todos los compuestos hasta $N$ ya fueron tachados. Los sobrevivientes son exactamente los primos $\le N$.

**¿Por qué basta cribar hasta $\sqrt{N}$?** Todo compuesto $n \le N$ tiene un factor primo $p \le \sqrt{n} \le \sqrt{N}$. Luego, cuando hemos procesado todos los primos $\le \sqrt{N}$, todos los compuestos ya fueron marcados.

Ejemplo: todos los primos hasta 50

Aplicamos la criba hasta $N = 50$. Como $\sqrt{50} < 8$, solo necesitamos cribar con los primos $2, 3, 5, 7$.

Tachamos múltiplos de 2: $4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50$.

Tachamos múltiplos de 3 (no ya tachados): $9, 15, 21, 27, 33, 39, 45$.

Tachamos múltiplos de 5 (no ya tachados): $25, 35$.

Tachamos múltiplos de 7 (no ya tachados): $49$.

Sobreviven: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$. Hay 15 primos hasta 50.

La función $\pi(x)$: contando primos

Se define $\pi(x)$ como el **número de primos menores o iguales a $x$**. Por ejemplo, $\pi(10)=4$ (los primos $2,3,5,7$), $\pi(50)=15$, $\pi(100)=25$.

El Teorema del Número Primo (demostrado por Hadamard y de la Vallée Poussin en 1896) dice que $\pi(x) \sim \frac{x}{\ln x}$, es decir, $\lim_{x\to\infty} \frac{\pi(x)}{x/\ln x} = 1$.

Para olimpiadas, la estimación útil es: $\pi(x) \approx x/\ln x$ da el orden de magnitud correcto. Por ejemplo, $\pi(1000) = 168$ y $1000/\ln(1000) \approx 144$. No exacto, pero útil para argumentos de conteo.

Una cota que sí se puede demostrar elementalmente (Chebychev): existen constantes $c_1, c_2 > 0$ tales que $c_1 x/\ln x \le \pi(x) \le c_2 x/\ln x$ para todo $x \ge 2$.

Gaps entre primos y primos gemelos

El gap entre dos primos consecutivos $p_n$ y $p_{n+1}$ es $p_{n+1} - p_n$. Los primeros gaps son $1$ (entre $2$ y $3$), $2, 2, 4, 2, 4, 2, 4, 6, 2, 6, \ldots$

Los gaps pueden ser arbitrariamente grandes: los $n-1$ números $n!+2, n!+3, \ldots, n!+n$ son todos compuestos (pues $k \mid n!+k$ para $2 \le k \le n$). Así hay runs de $n-1$ compuestos consecutivos.

Los primos gemelos son pares $(p, p+2)$ ambos primos: $(3,5), (5,7), (11,13), (17,19), (29,31), \ldots$ La conjetura de los primos gemelos —que hay infinitos pares gemelos— sigue abierta. Es uno de los problemas no resueltos más famosos de la teoría de números.

Postulado de Bertrand (que demostraremos en la lección 2.4): para todo $n \ge 1$, existe un primo $p$ con $n < p \le 2n$. Equivalentemente, $p_{n+1} < 2p_n$: los primos no se alejan demasiado.

Complejidad de la criba y variantes

La criba de Eratóstenes tiene complejidad temporal $O(N \log \log N)$ y espacial $O(N)$. Para $N = 10^6$ es perfectamente viable (millisegundos en computador).

Variante importante: la criba segmentada reduce la memoria a $O(\sqrt{N})$ dividiendo el intervalo $[1,N]$ en bloques de tamaño $\sqrt{N}$. Se usa cuando $N$ es muy grande (por ejemplo $N = 10^{10}$).

Para olimpiadas sin computador lo que importa es ejecutar la criba a mano hasta $N = 100$. Memoriza los primos hasta $100$: $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97$. Son 25. Ese dato —$\pi(100) = 25$— aparece en problemas de conteo.