Algoritmo para encontrar todos los números primos hasta n.
La Criba de Eratóstenes es un algoritmo fundamental y súper eficiente que sirve para identificar todos los números primos hasta un entero $n$ específico. A diferencia de la división por tentativa, que prueba si un número es primo intentando dividirlo entre enteros más chicos, la Criba funciona eliminando sistemáticamente los números compuestos de una lista. El proceso empieza con una lista de enteros del $2$ al $n$. Marcas el primer número, el $2$, como primo y tachas todos los múltiplos de $2$ (4, 6, 8, ...). Luego, el algoritmo se pasa al siguiente número disponible (que es el $3$), lo marca como primo y tacha todos sus múltiplos. Repites este ciclo para cada número que sigue y que todavía no has tachado.
Esta técnica es muy importante en las olimpiadas de matemáticas para problemas que involucran la distribución de primos, calcular la suma de primos en un rango o determinar la cantidad de primos $\pi(n)$ para valores moderados de $n$. Un truco clave que optimiza la Criba es que, para cualquier número compuesto $c$, debe existir un factor primo $p$ tal que $p \le \sqrt{c}$. Por lo tanto, cuando estés cribando hasta $n$, solo necesitas realizar el proceso de eliminación para los primos $p \le \sqrt{n}$. Además, al eliminar los múltiplos de un primo $p$, puedes empezar a tachar números desde $p^2$, ya que todos los múltiplos