🔢 Criba de Eratóstenes — Buscador Animado de Números Primos

Cualquier múltiplo compuesto de p menor que p² — como 2p, 3p, …, (p−1)p — ya tiene un factor primo menor que p, por lo que fue eliminado en una pasada anterior cuando se procesó ese primo menor. Comenzar cada pasada en p² evita trabajo redundante y es la optimización clave que le da a la criba su tiempo de ejecución O(N log log N) en lugar de un O(N log N) más lento.

La vista de la espiral de Ulam toma exactamente el mismo arreglo de criba usado en la vista de cuadrícula y vuelve a trazar cada primo superviviente a lo largo de un camino en espiral cuadrada que se enrolla hacia afuera desde el centro, una celda por entero. Visualmente, los primos tienden a agruparse a lo largo de ciertas líneas diagonales en esta disposición — un patrón sorprendente, aún no completamente explicado, observado por primera vez por el matemático Stanisław Ulam en 1963 mientras garabateaba durante una charla aburrida en una conferencia.

π(x) es la función de conteo de primos: el número real de primos menores o iguales a x, calculado directamente a partir de la criba mientras se ejecuta. x/ln(x) es la aproximación asintótica de orden principal del Teorema de los Números Primos (demostrado de forma independiente por Hadamard y de la Vallée Poussin en 1896). Las dos curvas se siguen cada vez más de cerca a medida que N crece, que es exactamente lo que predice el teorema — aunque la razón solo converge a 1 en el límite x → ∞.

El trabajo total es proporcional a N multiplicado por la suma de 1/p sobre todos los primos p ≤ √N (un "golpe" por cada múltiplo de cada primo). Según el segundo teorema de Mertens, la suma de los recíprocos de los primos hasta una cota crece como el logaritmo del logaritmo de esa cota, así que el trabajo total escala como N·log log N — asintóticamente cercano a lineal y mucho más rápido que dividir cada número individualmente por prueba.

Informa la mayor diferencia entre primos consecutivos encontrada hasta el límite N actual (por ejemplo, el hueco de 8 entre 89 y 97). Los huecos primos crecen de forma irregular pero en promedio se amplían como ln(N) a medida que N aumenta, según el Teorema de los Números Primos; la conjetura de Cramér propone una cota más ajustada sobre cuán grande puede llegar a ser cualquier hueco individual, pero sigue sin demostrarse.

No — la criba puede enumerar cada par de primos gemelos (p, p+2) por debajo de cualquier límite N que elijas, pero eso solo confirma finitos ejemplos. La conjetura de los primos gemelos afirma que existen infinitos pares de este tipo, lo cual es una afirmación sobre todos los primos, no un cálculo finito; a pesar de una fuerte evidencia numérica y parcialmente teórica (incluyendo el avance de huecos acotados de Zhang en 2013), sigue siendo un problema abierto en la teoría de números.