Usar la criba para contar cuántos primos hay hasta n.
El conteo de primos consiste en determinar cuántos números primos son menores o iguales a un número real $x$ dado. A este conteo lo representas con la función $\pi(x)$. Aunque para números muy pequeños podrías simplemente enlistar los primos, para límites más grandes (comunes en competencias como el AMC 10), vas a depender de la lógica de la Criba de Eratóstenes. La idea fundamental de la Criba es que para identificar los primos hasta $n$, solo necesitas eliminar los múltiplos de los números primos $p$ donde $p \le \sqrt{n}$. Cualquier número compuesto $n$ debe tener un factor primo menor o igual a su raíz cuadrada; si quitas todos esos múltiplos, los números que quedan son primos.
En teoría de números computacional y en matemáticas de olimpiada, puedes aplicar este proceso de cribado usando el Principio de Inclusión-Exclusión (PIE) en lugar de tachar números manualmente en una lista. Para contar los números que quedan después de la criba, empieza con el total de enteros, resta los múltiplos de los primos, vuelve a sumar los múltiplos de los productos de pares de primos (que restaste dos veces), resta los múltiplos de productos de tríos, y así sucesivamente. A este cálculo lo puedes formalizar como la Fórmula de Legendre.
Esta técnica es crucial para resolver problemas que piden la cantidad de primos en un rango específico o para determinar si un entero en particular es primo. Transforma el problema de una búsqueda de divisores a un ejercicio de conteo sistemático. Dominar este tema requiere que entiendas tanto el límite $\sqrt{n}$ para la eficiencia como la mecánica de inclusión-exclusión para calcular con precisión.
1. La Función de Conteo de Primos La función $\pi(x)$ cuenta la cantidad de primos $p$ tales que $p \le x$: $$ \pi(x) = \sum_{p \le x} 1 $$
2. El Límite de la Criba Para determinar los primos hasta $n$, o para checar si $n$ es primo, solo necesitas probar la divisibilidad entre primos $p$ que cumplan: $$ p \le \sqrt{n} $$
3. Fórmula de Legendre (Criba mediante Inclusión-Exclusión) Para contar la cantidad de primos hasta $x$, toma a $p_1, p_2, \dots, p_k$ como los primos distintos menores o iguales a $\sqrt{x}$. La cantidad de primos hasta $x$ viene dada por: $$ \pi(x) = \pi(\sqrt{x}) - 1 + \sum_{d | P} \mu(d) \left\lfloor \frac{x}{d} \right\rfloor $$ Donde $P = p_1 p_2 \dots p_k$, y $\mu(d)$ es la función de Möbius. En su forma expandida de Inclusión-Exclusión: $$ \pi(x) \approx \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 - \sum \left\lfloor \frac{x}{p_i p_j p_l} \right\rfloor + \dots $$ (Nota: El término $\pi(\sqrt{x}) - 1$ toma en cuenta a los mismos primos $\le \sqrt{x}$, que la fórmula "elimina" pero que en realidad son primos, menos el número 1).
Teorema: Si un entero $n > 1$ es compuesto, entonces $n$ tiene un divisor primo $p$ tal que $p \le \sqrt{n}$.
Demostración:
Suposición: Toma a $n$ como un entero compuesto tal que $n > 1$.
Definición de Compuesto: Por la definición de un número compuesto, existen enteros $a$ y $b$ tales que $n = ab$, con $1 < a < n$ y $1 < b < n$.
Demostración por Contradicción: Supón por contradicción que $n$ no tiene divisores menores o iguales a $\sqrt{n}$. Como $a$ y $b$ son divisores de $n$, esta suposición implica que tanto $a > \sqrt{n}$ como $b > \sqrt{n}$.
Análisis de Desigualdades: Si multiplicas estas desigualdades, obtienes: $$ a \cdot b > \sqrt{n} \cdot \sqrt{n} $$ $$ ab > n $$
Contradicción: Sin embargo, en el paso 2 viste que $ab = n$. La desigualdad $ab > n$ contradice la igualdad $ab = n$.
Conclusión sobre los Divisores: Por lo tanto, la suposición debe ser falsa. Al menos uno de los divisores $a$ o $b$ debe ser menor o igual a $\sqrt{n}$. Supón sin pérdida de generalidad que $a \le \sqrt{n}$.
Factorización Prima: Como $a > 1$, por el Teorema Fundamental de la Aritmética, $a$ debe tener al menos un factor primo $p$. Como $p$ divide a $a$ y $a$ divide a $n$, $p$ tiene que dividir a $n$. Además, como $p \le a$ y $a \le \sqrt{n}$, se sigue que $p \le \sqrt{n}$.
Así, todo número compuesto $n$ tiene un factor primo $p \le \sqrt{n}$. Esto demuestra que la Sieve of Eratosthenes solo requiere cribar con los primos hasta $\sqrt{n}$ para identificar todos los primos hasta $n$.
$\square$