Tachar los múltiplos de cada número primo.
La Criba de Eratosthenes es un algoritmo fundamental en teoría de números que sirve para identificar todos los números primos hasta un entero específico $N$. A diferencia de la división por tentativa, que prueba si cada número es primo uno por uno, la Criba funciona eliminando poco a poco los números compuestos de una lista. El proceso empieza con una lista de enteros del $2$ al $N$. El algoritmo identifica el primer número que no está marcado (que es el $2$) como primo, y luego marca todos los múltiplos de $2$ como compuestos. Después sigue con el siguiente número sin marcar (que es el $3$), lo identifica como primo y marca todos los múltiplos de $3$. Esto sigue así hasta que el algoritmo llega a la raíz cuadrada de $N$.
Esta técnica es súper eficiente y es el método estándar para generar listas de primos en programación competitiva y matemáticas. La idea clave que hace que el algoritmo sea tan eficiente es que un número compuesto $n$ debe tener un factor primo $p$ tal que $p \le \sqrt{n}$. Por eso, solo necesitas cribar usando primos hasta $\sqrt{N}$. Además, cuando estés cribando con un primo $p$, puedes empezar a marcar los múltiplos desde $p^2$, porque cualquier múltiplo más chico $k \cdot p$ (donde $k < p$) ya lo habrán marcado los factores primos de $k$.
En el contexto del AMC 8 y AMC 10, vas a usar la Criba seguido de forma manual para rangos pequeños (por ejemplo, para encontrar primos hasta el 100) o de forma conceptual para resolver problemas sobre la densidad de primos, propiedades de divisibilidad o el Principio de Inclusión-Exclusión. Sirve como base para métodos de cribado más avanzados que se usan para estimar la función de conteo de primos $\pi(x)$.
1. El Límite del Factor Primo Un número $n$ es compuesto si y solo si tiene un factor primo $p$ que cumple: $$p \le \sqrt{n}$$ Por lo tanto, para cribar hasta $N$, solo tienes que iterar por los primos $p$ donde $p \le \sqrt{N}$.
2. Optimización del Índice de Inicio Cuando marques los múltiplos de un primo $p$, el primer múltiplo que necesitas marcar es $p^2$. Los múltiplos los marcas en los índices: $$p^2, p^2 + p, p^2 + 2p, \dots, p^2 + k \cdot p \le N$$
3. Fórmula de Legendre (Criba Teórica) El número de primos hasta $x$, que escribes como $\pi(x)$, lo puedes calcular usando el Principio de Inclusión-Exclusión basado en la lógica de la Criba. Si $p_1, p_2, \dots, p_k$ son los primos menores o iguales a $\sqrt{x}$: $$\pi(x) - \pi(\sqrt{x}) + 1 = \lfloor x \rfloor - \sum \left\lfloor \frac{x}{p_i} \right\rfloor + \sum \left\lfloor \frac{x}{p_i p_j} \right\rfloor - \dots$$
4. Complejidad Temporal La complejidad computacional de la Criba de Eratosthenes para encontrar todos los primos hasta $N$ es: $$O(N \log \log N)$$
Teorema: La Criba de Eratosthenes identifica correctamente un número $n$ (donde $1 < n \le N$) como primo si y solo si queda sin marcar después de cribar con todos los primos $p \le \sqrt{N}$.
Demostración:
Hay que mostrar dos cosas: (1) El algoritmo marca todos los números compuestos, y (2) El algoritmo no marca ningún número primo.
Parte 1: El algoritmo marca todos los números compuestos. Toma un número compuesto $n$ tal que $n \le N$. Por la definición de número compuesto, puedes escribir $n$ como $n = a \cdot b$ donde $1 < a, b < n$. Supón sin perder generalidad que $a \le b$. Entonces $a^2 \le ab = n$, lo que implica que $a \le \sqrt{n} \le \sqrt{N}$. Como $a > 1$, $a$ debe tener un factor primo $p$. Así que $p \le a \le \sqrt{N}$. Como $p$ es un factor primo de $a$, y $a$ es un factor de $n$, entonces $p$ divide a $n$. Por lo tanto, $n$ es un múltiplo de $p$. Como $p \le \sqrt{N}$, el algoritmo eventualmente va a elegir a $p$ como un primo para cribar. En este paso, todos los múltiplos de $p$ (incluyendo $n$) quedan marcados. Así, todos los números compuestos se marcan.
Parte 2: El algoritmo no marca ningún número primo. Toma un número primo $q$ tal que $q \le N$. Un número queda marcado solo si es múltiplo de algún primo $p$ más chico (donde $p$ es el primo actual de la criba). Para que $q$ quedara marcado, tendría que existir un primo $p < q$ tal que $p$ divida a $q$. Pero, por definición, un número primo $q$ no tiene más divisores que el $1$ y él mismo. Por lo tanto, no existe ningún primo $p < q$ que divida a $q$. En consecuencia, $q$ nunca se marca.
Conclusión: Como el algoritmo marca todos los números compuestos y no marca ningún número primo, el conjunto de números sin marcar que quedan al final es exactamente el conjunto de los números primos hasta $N$.
$\square$