Generador de la Criba de Eratóstenes (Gratis) – Lista de primos y n-ésimo primo
Introduce un límite superior N para generar una lista de números primos con la Criba de Eratóstenes, visualizada paso a paso. Busca también el n-ésimo primo (hasta el 1.000.000) — gratis, en el navegador, sin registro.
Criba de Eratóstenes del 1 al 100 (tabla de referencia)
Las celdas verdes son números primos; el resto fueron eliminados por la criba.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
El 1 no es ni primo ni compuesto, por lo que no se colorea.
Qué hace la criba de Eratóstenes
La criba de Eratóstenes es el algoritmo clásico para encontrar números primos, que debe su nombre al sabio griego del siglo III a. C. La idea resulta asombrosamente simple: tome cada número por orden a partir del dos, declárelo primo si no ha sido tachado todavía y tache a continuación todos sus múltiplos. Tache los múltiplos de dos, luego los del tres que ha sobrevivido, después los del cinco; repita hasta la raíz cuadrada de su límite y todo número que siga en pie será primo.
Indique a esta herramienta un límite superior y generará la lista de primos hasta un millón. Muestra el proceso de tachado paso a paso, de modo que puede seguir con sus propios ojos qué primo eliminó qué números. También funciona a la inversa y responde a la pregunta «¿cuál es el primo número N?» para posiciones tan altas como la millonésima. Todo se calcula en su navegador, así que nada de lo que introduzca sale de él.
Cómo generar una lista de primos
- Introduzca el límite superior N Indique un entero entre 2 y 1.000.000. Empezar por algo pequeño como 100 hace mucho más visible el mecanismo de la criba.
- Compruebe el recuento y el mayor primo Obtiene cuántos primos hay hasta N —lo que se escribe π(N)— y el mayor de ellos.
- Siga los pasos del tachado Con límites pequeños, cada etapa muestra qué primo se empleó y qué números eliminó.
- Busque el primo número N Introduzca una posición y la herramienta devuelve el primo que la ocupa.
Consejos para aprovecharla mejor
- La Criba de Eratóstenes lista eficientemente todos los primos hasta N tachando los múltiplos de cada primo encontrado, empezando por el 2.
- Configura el límite superior N en 400 o menos para ver exactamente qué primo eliminó cada número, paso a paso.
- La búsqueda del n-ésimo primo admite consultas como "cuál es el primo número 1.000.000", útil para confirmar la existencia de primos muy grandes.
- Todo se ejecuta localmente en tu navegador — la lista de primos generada nunca se envía a un servidor.
Situaciones en las que resulta útil
Estudiar algoritmos
La criba es el ejemplo de manual de la complejidad O(n log log n), y verla funcionar fija la idea.
Verificar su propia implementación
Compare la salida de una criba escrita por usted con esta para confirmar que produce la secuencia correcta.
Observar cómo se distribuyen los primos
Variar el límite y observar cómo crece π(N) da idea del teorema de los números primos y su comportamiento aproximado N / log N.
Documentarse sobre criptografía
Los esquemas de clave pública como RSA descansan en primos grandes, y esta es una vía de entrada para captar con qué densidad aparecen.
Términos de primos y cribas
- Número primo
- Un número natural mayor o igual que dos cuyos únicos divisores positivos son el uno y él mismo. El uno no cuenta como primo.
- Número compuesto
- Un número natural mayor o igual que dos que no es primo. Son los que la criba va tachando.
- π(N)
- La función que da el recuento de primos hasta N, conocida como función contadora de primos.
- Tachado
- Marcar los múltiplos de un primo para excluirlos de los candidatos. La operación es la que da nombre al algoritmo.
- Por qué basta la raíz cuadrada
- Todo múltiplo de un primo mayor que la raíz cuadrada de N ya ha sido tachado como múltiplo de algún primo menor.
- Teorema de los números primos
- El resultado según el cual π(N) es asintótica a N / log N, que describe con qué rapidez se enrarecen los primos.
Preguntas frecuentes
A propósito — Por qué un algoritmo de 2.000 años sigue en uso
La Criba de Eratóstenes es uno de los algoritmos generadores de primos más antiguos que se conservan, atribuido al erudito griego Eratóstenes, que fue bibliotecario jefe de la Biblioteca de Alejandría en el siglo III a.C. Que un método concebido hace más de dos mil años siga enseñándose hoy en cursos de informática habla de su elegante simplicidad.
El mecanismo es sorprendentemente simple: se listan los enteros desde el 2, se toma el menor número aún no marcado como primo, y se tachan todos sus múltiplos. Repitiendo esto hasta √N se obtienen todos los primos hasta N. Para generar una lista completa de primos, esto es mucho más eficiente que probar cada número individualmente con la división de prueba.
La búsqueda de primos enormes continúa hoy en día — proyectos de computación distribuida como GIMPS (la Gran Búsqueda de Primos de Mersenne por Internet) siguen descubriendo primos de Mersenne con decenas de millones de dígitos. La criba en sí no se usa para encontrar primos tan grandes, pero su idea central — eliminar múltiplos mecánicamente — sustenta algoritmos de comprobación de primalidad más avanzados.