Complejidad Temporal
Mejor: O(n log log n)
Prom: O(n log log n)
Peor: O(n log log n)
La Criba de Eratóstenes es un algoritmo clásico para encontrar todos los números primos hasta un límite n. Funciona marcando iterativamente los múltiplos de cada primo, empezando por 2.
Cómo funciona:
1. Crea un arreglo booleano marcando 2..n como potencialmente primos
2. Para cada i desde 2 hasta √n, si i sigue marcado como primo, marca todos sus múltiplos (empezando desde i²) como compuestos
3. Los números que permanezcan marcados al terminar el bucle son los primos ≤ n
¿Por qué empezar a tachar desde i²?
Todos los múltiplos menores de i (2i, 3i, …, (i−1)i) ya fueron tachados por un primo más pequeño.
Complejidad Temporal:
Mejor: O(n log log n)
Promedio: O(n log log n)
Peor: O(n log log n)
Complejidad Espacial: O(n)
Propiedades:
- Determinista, sin aleatoriedad
- Eficiente en caché cuando n cabe en memoria
- Fundamento para teoría de números y preprocesamiento criptográfico
Lleva el nombre del matemático griego Eratóstenes de Cirene (~276–194 a.C.). Esta criba sigue siendo una de las formas más eficientes de encontrar todos los primos pequeños y es la base de muchos pasos de preprocesamiento para factorización.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Criba de Eratóstenes?
- La Criba de Eratóstenes es un algoritmo clásico para encontrar todos los números primos hasta un límite n. Funciona marcando iterativamente los múltiplos de cada primo, empezando por 2.
- ¿Cuál es la complejidad de Criba de Eratóstenes?
- Tiempo (promedio): O(n log log n) · Espacio: O(n)
- ¿Para quién es este visualizador de Criba de Eratóstenes?
- La visualización de Criba de Eratóstenes está pensada para nivel intermedio, dentro de la categoría Matemáticas. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Criba de Eratóstenes?
- En la misma categoría (Matemáticas) puedes explorar: Euclidean Algorithm. Todos tienen visualización interactiva.