Criba de Eratóstenes
Enumere todos los primos hasta N en tiempo casi lineal
Criba de Eratóstenes es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Primos en masa
A veces necesita todos los primos hasta N, no solo una comprobación. La criba de Eratóstenes los encuentra todos en un solo recorrido. 🧹
La idea principal
Comience suponiendo que todos los números son primos. Después, tache los múltiplos de cada primo que encuentre y deje únicamente los primos verdaderos.
Configure las marcas
Cree una lista booleana donde el índice i indique si i es primo. Este arreglo es el lienzo sobre el que trabaja la criba.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalseRecorra los candidatos
Avance i hacia arriba. La primera vez que llegue a un número que aún tenga la marca True, debe ser un primo nuevo sin ningún factor menor.
Tache los múltiplos
Para cada primo i, marque 2i, 3i, 4i y así sucesivamente como no primos. Esos múltiplos tienen claramente a i como divisor.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseComience en i al cuadrado
Comience a tachar en i*i, no en 2i. Todos los múltiplos menores ya fueron eliminados por un primo anterior, así que puede omitirlos.
Deténgase en la raíz
Solo necesita ejecutar la criba mientras i*i sea menor o igual que N. Después de la raíz cuadrada, toda marca True restante ya corresponde a un primo.
La criba completa
Combine el recorrido externo con el tachado interno. Después del bucle, cada índice que conserve la marca True será un primo confirmado.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseReúna los primos
Lea las marcas finales para crear una lista mediante una comprensión. Ahora tiene todos los primos hasta N, listos para realizar consultas rápidas.
primes = [i for i, p in enumerate(is_prime) if p]Por qué es rápida
La criba se ejecuta en aproximadamente O(n log log n), un tiempo casi lineal. Por eso supera ampliamente las comprobaciones repetidas de números individuales.
Tenga en cuenta la memoria
El arreglo de marcas utiliza una cantidad de memoria proporcional a N. Para límites muy grandes, revise su presupuesto de espacio antes de reservar memoria.
Comprobación rápida
Recuerde la pequeña optimización del bucle interno.
Repaso
Ahora puede construir una criba para listar todos los primos hasta N en tiempo casi lineal, comenzando cada primo en i*i y deteniéndose en la raíz. ✅
Preguntas frecuentes
¿La lección «Criba de Eratóstenes» es gratis?
Sí — el texto completo de «Criba de Eratóstenes» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Criba de Eratóstenes»?
Enumere todos los primos hasta N en tiempo casi lineal Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Criba de Eratóstenes»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- GCD, LCM y el algoritmo de Euclides
- Prueba de primalidad hasta sqrt(n)
- Criba de Eratóstenes
- Factorización prima y divisores