Sobre la criba de Eratóstenes - la criba de primos más antigua
La criba de Eratóstenes encuentra todos los números primos hasta un límite sin una sola división. Solo hay que contar: tacha uno de cada dos números después del 2, uno de cada tres después del 3, y así sucesivamente. Lo que queda son los primos. Más de dos mil años después, sigue siendo una de las formas más rápidas de listarlos.
Eratóstenes de Cirene
Eratóstenes vivió aproximadamente entre el 276 y el 194 a. C. y dirigió la gran biblioteca de Alejandría. Es conocido sobre todo por medir el tamaño de la Tierra a partir de la longitud de las sombras en dos ciudades. La criba lleva su nombre porque Nicómaco de Gerasa la describió como su método en la Introducción a la aritmética, escrita hacia el año 100.
Cómo funciona la criba
Escribe los números del 2 al N. El primero, 2, es primo: tacha 4, 6, 8 y todos los demás múltiplos de 2. El siguiente número que queda, 3, es primo: tacha 9, 12, 15 y así sucesivamente. Sigue con 5, 7 y los siguientes números que queden. Un número que nunca se tacha no tiene ningún factor menor, así que es primo.
Parar en la raíz cuadrada
Todo número compuesto hasta N tiene un factor primo que no es mayor que la raíz cuadrada de N. Así que, en cuanto p² supera N, ya no queda nada por tachar. Para los primos hasta 100 solo necesitas 2, 3, 5 y 7, y para 1000 los primos hasta 31.
¿Qué tan rápida es?
La criba necesita unos N log log N pasos, que crecen solo un poco más rápido que el propio N. Los ordenadores aún la usan, a menudo por tramos en forma de criba segmentada, para listar primos hasta miles de millones. Para comprobar si un solo número grande es primo, otros métodos son más rápidos.
Preguntas frecuentes
¿Quién inventó la criba de Eratóstenes?
Lleva el nombre de Eratóstenes de Cirene, un sabio griego del siglo III a. C. La descripción escrita más antigua es de Nicómaco de Gerasa, hacia el año 100.
¿Por qué la criba empieza a tachar en p²?
Todo múltiplo menor de p tiene un factor primo menor, así que un primo menor ya lo ha tachado.
¿Cuántos primos hay por debajo de 1000?
Hay 168 primos por debajo de 1000. El mayor es 997.
Herramientas relacionadas
Criba de Eratóstenes
Mira cómo la criba de Eratóstenes encuentra los números primos hasta 100, 200, 500 o 1000. Cada primo tacha sus múltiplos con su propio color, paso a paso.
Espiral de Ulam
Dibuja la espiral de Ulam en tu navegador. Marca los primos, lee el polinomio cuadrático de cada diagonal y abre la racha ininterrumpida de 40 primos de Euler.
La espiral de Ulam
Cómo la espiral de Stanisław Ulam de 1963 coloca los enteros en una cuadrícula, por qué los primos se agrupan en diagonales cuadráticas y dónde están los cuarenta primos de Euler cuando la espiral empieza en 41.
La conjetura de Collatz
Explora el problema de Collatz 3n+1 en tu navegador. Recorre secuencias de granizo, haz crecer un árbol de Collatz geométrico y haz zoom en el fractal de Collatz continuo.
¿Listo para probarlo?
Abra PictorX en su navegador: no requiere instalación ni tarjeta de crédito para comenzar.
Probar la criba de Eratóstenes