En teoría de números, la Criba de Eratóstenes es un algoritmo eficiente para encontrar todos los números primos menores o iguales a un número dado \(n\). Se basa en la eliminación iterativa de múltiplos de cada número primo a partir de \(2\), permitiendo determinar la primalidad de los números de forma rápida.
Definición y Algoritmo
El objetivo del algoritmo es generar la lista de todos los primos menores o iguales a \(n\). La idea es marcar como compuestos los múltiplos de cada primo, dejando como primos los números no marcados. Su implementación sigue estos pasos:
- Se crea una lista de booleanos \(A\) de tamaño \(n+1\) donde todos los valores están inicialmente en verdadero (indicando que los números son primos).
- Se establece que \(A[0]\) y \(A[1]\) sean falsos, ya que \(0\) y \(1\) no son primos.
- Se inicia un bucle desde \(p = 2\) hasta \(\sqrt{n}\):
- Si \(A[p]\) es verdadero, entonces \(p\) es primo.
- Se marcan como falsos todos los múltiplos de \(p\) mayores o iguales a \(p^2\).
- Al finalizar el proceso, los índices que permanecen en verdadero en \(A\) corresponden a números primos.
Representación Matemática del Algoritmo
Dado un número entero \(n\), el algoritmo trabaja sobre el conjunto: $$ \huge S = \{2, 3, 4, \dots, n\} $$ Para cada número primo \(p\), se eliminan sus múltiplos: $$ \huge p^2, p^2 + p, p^2 + 2p, \dots, n $$
Siendo la complejidad temporal del algoritmo: $$ \huge O(n \log \log n) $$
lo que lo hace eficiente en comparación con la verificación individual de la primalidad de cada número.
Ejemplo de Aplicación
Para \(n = 30\), se construye la lista inicial: $$ 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 $$
- Se empieza con \(p = 2\) y se eliminan \(4, 6, 8, 10, \dots, 30\).
- Se sigue con \(p = 3\) y se eliminan \(9, 12, 15, 18, \dots, 30\).
- Se continúa con \(p = 5\), eliminando \(25, 30\).
Los números restantes son primos: $$ \Large 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 $$
Aplicaciones de la Criba de Eratóstenes
- Generación de números primos en criptografía: Se utiliza en la generación de claves en algoritmos como RSA.
- Optimización de algoritmos en teoría de números: Es útil en problemas que requieren listas de primos de forma rápida.
- Cálculo de funciones aritméticas: Se emplea en la determinación de la función \(\varphi(n)\) de Euler o en la factorización eficiente de números.
Conclusión
La Criba de Eratóstenes es un algoritmo fundamental en teoría de números debido a su eficiencia y simplicidad. Su aplicación en múltiples áreas matemáticas y computacionales la convierte en una herramienta esencial para la generación de números primos.
