Tamiz de Eratóstenes - Sieve of Eratosthenes
En matemáticas , el tamiz de Eratóstenes es un algoritmo antiguo para encontrar todos los números primos hasta un límite determinado.
Lo hace marcando iterativamente como compuestos (es decir, no primos) los múltiplos de cada primo, comenzando con el primer número primo, 2. Los múltiplos de un número primo dado se generan como una secuencia de números que comienzan desde ese primo, con diferencia constante entre ellos que es igual a ese primo. Esta es la distinción clave del tamiz del uso de la división de prueba para probar secuencialmente cada número candidato para determinar la divisibilidad por cada primo. Una vez que todos los múltiplos de cada número primo descubierto se han marcado como compuestos, los números restantes sin marcar son números primos.
La primera referencia conocida al tamiz ( griego antiguo : κόσκινον Ἐρατοσθένους , kóskinon Eratosthénous ) se encuentra en la Introducción a la aritmética de Nicomachus de Gerasa , de principios del siglo II. CE libro, que lo describe y atribuye a Eratóstenes de Cirene , un 3er ciento. AEC matemático griego .
Uno de varios filtros de números primos , es una de las formas más eficientes de encontrar todos los números primos más pequeños. Puede usarse para encontrar números primos en progresiones aritméticas .
Visión general
Tamizar los dos y tamizar los tres:
el tamiz de Eratóstenes.
Cuando los múltiplos sublimes,
los números que quedan son primos.
Anónimo
Un número primo es un número natural que tiene exactamente dos divisores de números naturales distintos : el número 1 y él mismo.
Para encontrar todos los números primos menores o iguales a un entero n dado por el método de Eratóstenes:
- Cree una lista de números enteros consecutivos del 2 al n : (2, 3, 4, ..., n ) .
- Inicialmente, sea p igual a 2, el número primo más pequeño.
- Enumerar los múltiplos de p contando en incrementos de p de 2 p a n , y marcarlos en la lista (estos serán 2 p , 3 p , 4 p , ... , el p en sí no debe ser marcado).
- Encuentra el número más pequeño de la lista mayor que p que no está marcado. Si no existía tal número, deténgase. De lo contrario, sea p ahora igual a este nuevo número (que es el siguiente primo), y repita desde el paso 3.
- Cuando el algoritmo termina, los números que quedan sin marcar en la lista son todos los números primos debajo de n .
La idea principal aquí es que todo valor dado ap será primo, porque si fuera compuesto se marcaría como un múltiplo de algún otro primo más pequeño. Tenga en cuenta que algunos de los números pueden estar marcados más de una vez (por ejemplo, 15 se marcará tanto para 3 como para 5).
Como refinamiento, es suficiente marcar los números en el paso 3 comenzando desde p 2 , ya que todos los múltiplos más pequeños de p ya se habrán marcado en ese punto. Esto significa que se permite que el algoritmo termine en el paso 4 cuando p 2 es mayor que n .
Otro refinamiento es enumerar inicialmente solo los números impares, (3, 5, ..., n ) , y contar en incrementos de 2 p desde p 2 en el paso 3, marcando así solo los múltiplos impares de p . En realidad, esto aparece en el algoritmo original. Esto se puede generalizar con la factorización de la rueda , formando la lista inicial solo a partir de números coprime con los primeros números primos y no solo de probabilidades (es decir, números coprime con 2), y contando en los incrementos ajustados correspondientemente de modo que solo esos múltiplos de p sean generados que son coprime con esos pequeños números primos, en primer lugar.
Ejemplo
Para encontrar todos los números primos menores o iguales que 30, proceda de la siguiente manera.
Primero, genere una lista de números enteros del 2 al 30:
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
El primer número de la lista es 2; tacha cada segundo número en la lista después de 2 contando desde 2 en incrementos de 2 (estos serán todos los múltiplos de 2 en la lista):
2 3456789101112131415161718192021222324252627282930
El siguiente número en la lista después del 2 es 3; tacha cada tercer número en la lista después de 3 contando desde 3 en incrementos de 3 (estos serán todos los múltiplos de 3 en la lista):
2 3456789101112131415161718192021222324252627282930
El siguiente número aún no tachado en la lista después del 3 es el 5; tacha cada quinto número de la lista después de 5 contando desde 5 en incrementos de 5 (es decir, todos los múltiplos de 5):
2 3456789101112131415161718192021222324252627282930
El siguiente número aún no tachado en la lista después del 5 es 7; el siguiente paso sería tachar cada séptimo número en la lista después del 7, pero todos ya están tachados en este punto, ya que estos números (14, 21, 28) también son múltiplos de números primos más pequeños porque 7 × 7 es mayor que 30. Los números que no están tachados en este punto de la lista son todos los números primos por debajo de 30:
2 3 5 7 11 13 17 19 23 29
Algoritmo y variantes
Pseudocódigo
El tamiz de Eratóstenes se puede expresar en pseudocódigo , de la siguiente manera:
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.
let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n do
if A[i] is true
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
A[j] := false
return all i such that A[i] is true.
Este algoritmo produce todos los números primos no mayores que n . Incluye una optimización común, que es comenzar a enumerar los múltiplos de cada primo i de i 2 . La complejidad temporal de este algoritmo es O ( n log log n ) , siempre que la actualización de la matriz sea una operación O (1) , como suele ser el caso.
Tamiz segmentado
Como señala Sorenson, el problema con el tamiz de Eratóstenes no es la cantidad de operaciones que realiza, sino más bien sus requisitos de memoria. Para n grandes , es posible que el rango de números primos no quepa en la memoria; peor aún, incluso para n moderado , su uso de caché es muy subóptimo. El algoritmo recorre toda la matriz A , sin mostrar casi ninguna localidad de referencia .
Una solución a estos problemas la ofrecen los tamices segmentados , en los que solo se tamizan a la vez partes de la gama. Estos se conocen desde la década de 1970 y funcionan de la siguiente manera:
- Divida el rango de 2 a n en segmentos de algún tamaño Δ ≤ √ n .
- Encuentre los números primos en el primer segmento (es decir, el más bajo), usando el tamiz regular.
- Para cada uno de los siguientes segmentos, en orden creciente, siendo m el valor más alto del segmento, encuentre los números primos en él de la siguiente manera:
- Configure una matriz booleana de tamaño Δ y
- Marque como no primos las posiciones en la matriz correspondientes a los múltiplos de cada primo p ≤ √ m encontrado hasta ahora, calculando el múltiplo más bajo de p entre m - Δ y m , y enumerando sus múltiplos en pasos de p como de costumbre. Las posiciones restantes corresponden a los primos en el segmento, ya que el cuadrado de un primo en el segmento no está en el segmento (para k ≥ 1 , uno tiene ).
Si se elige que Δ sea √ n , la complejidad espacial del algoritmo es O ( √ n ) , mientras que la complejidad temporal es la misma que la del tamiz regular.
Para rangos con límite superior n tan grande que los cebadores de tamizado por debajo de √ n como lo requiere el tamiz segmentado de página de Eratóstenes no pueden caber en la memoria, se puede usar un tamiz más lento pero mucho más eficiente en el espacio como el tamiz de Sorenson .
Tamiz incremental
Una formulación incremental del tamiz genera primos indefinidamente (es decir, sin un límite superior) intercalando la generación de primos con la generación de sus múltiplos (de modo que los primos se puedan encontrar en espacios entre los múltiplos), donde los múltiplos de cada primo p se generan directamente contando desde el cuadrado del primo en incrementos de p (o 2 p para primos impares). La generación debe iniciarse solo cuando se alcanza el cuadrado principal, para evitar efectos adversos sobre la eficiencia. Se puede expresar simbólicamente bajo el paradigma del flujo de datos como
primes = [2, 3, ...] \ [[p², p²+p, ...] for p in primes],
usando la notación de comprensión de listas para \denotar la resta de conjuntos de progresiones aritméticas de números.
Los primos también se pueden producir tamizando iterativamente los compuestos mediante pruebas de divisibilidad mediante primos secuenciales, uno a la vez. No es el tamiz de Eratosthenes pero a menudo se confunde con él, a pesar de que el tamiz de Eratosthenes genera directamente los compuestos en lugar de probarlos. La división de prueba tiene una complejidad teórica peor que la del tamiz de Eratóstenes en la generación de rangos de primos.
Al probar cada primo, el algoritmo de división de prueba óptimo usa todos los números primos que no exceden su raíz cuadrada, mientras que el tamiz de Eratóstenes produce cada compuesto a partir de sus factores primos únicamente, y obtiene los primos "gratis" entre los compuestos. El código de tamiz funcional de 1975 ampliamente conocido de David Turner se presenta a menudo como un ejemplo del tamiz de Eratóstenes, pero en realidad es un tamiz de división de prueba subóptimo.
Complejidad algorítmica
El tamiz de Eratóstenes es una forma popular de comparar el rendimiento de la computadora. La complejidad temporal de calcular todos los números primos por debajo de n en el modelo de máquina de acceso aleatorio es operaciones O ( n log log n ) , una consecuencia directa del hecho de que la serie de armónicos primos se acerca asintóticamente a log log n . Sin embargo, tiene una complejidad de tiempo exponencial con respecto al tamaño de entrada, lo que lo convierte en un algoritmo pseudopolinomial . El algoritmo básico requiere O ( n ) de memoria.
La complejidad de bits del algoritmo es O ( n (log n ) (log log n ) ) operaciones de bits con un requisito de memoria de O ( n ) .
La versión segmentada de página implementada normalmente tiene la misma complejidad operativa de O ( n log log n ) que la versión no segmentada, pero reduce los requisitos de espacio al tamaño mínimo de la página de segmento más la memoria necesaria para almacenar los números primos base menos de la raíz cuadrada del rango utilizado para seleccionar compuestos de segmentos de página sucesivos de tamaño O ( √ n/log n) .
Una versión segmentada especial (rara vez o nunca implementada) del tamiz de Eratóstenes, con optimizaciones básicas, utiliza operaciones O ( n ) y O ( √ nlog log n/log n) bits de memoria.
El uso de la notación O grande ignora los factores constantes y las compensaciones que pueden ser muy significativas para rangos prácticos: El tamiz de la variación de Eratóstenes conocido como el tamiz de rueda de Pritchard tiene un rendimiento O ( n ) , pero su implementación básica requiere un algoritmo de "una matriz grande" lo que limita su rango utilizable a la cantidad de memoria disponible, de lo contrario, necesita ser segmentado por páginas para reducir el uso de memoria. Cuando se implementa con la segmentación de la página para ahorrar memoria, el algoritmo básico aún requiere aproximadamente O (norte/log n) bits de memoria (mucho más que el requisito del tamiz segmentado de página básica de Eratóstenes usando O (√ n/log n) bits de memoria). El trabajo de Pritchard redujo el requisito de memoria a costa de un gran factor constante. Aunque el tamiz de rueda resultante tieneun rendimiento O ( n )y un requisito de memoria aceptable, no es más rápido que un tamiz básico de Eratóstenes razonablemente factorizado por rueda para rangos de tamizado prácticos.
Tamiz de Euler
La prueba de Euler de la fórmula del producto zeta contiene una versión del tamiz de Eratosthenes en la que cada número compuesto se elimina exactamente una vez. El mismo tamiz fue redescubierto y observó a tomar tiempo lineal por Gries y Misra (1978) . También comienza con una lista de números del 2 al n en orden. En cada paso, el primer elemento se identifica como el siguiente primo, se multiplica con cada elemento de la lista (comenzando así por sí mismo) y los resultados se marcan en la lista para su posterior eliminación. El elemento inicial y los elementos marcados se eliminan de la secuencia de trabajo y se repite el proceso:
[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 ... [3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 ... [4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ... [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ... [...]
Aquí se muestra el ejemplo comenzando por las probabilidades, después del primer paso del algoritmo. Por lo tanto, en el k- ésimo paso, todos los múltiplos restantes del k- ésimo primo se eliminan de la lista, que a partir de entonces contendrá solo números coprime con los primeros k primos (cf. factorización de la rueda ), de modo que la lista comenzará con el siguiente. primo, y todos los números debajo del cuadrado de su primer elemento también serán primos.
Por lo tanto, cuando se genera una secuencia acotada de primos, cuando el siguiente primo identificado excede la raíz cuadrada del límite superior, todos los números restantes de la lista son primos. En el ejemplo anterior, eso se logra al identificar 11 como el próximo primo, dando una lista de todos los primos menores o iguales que 80.
Tenga en cuenta que los números que serán descartados por un paso todavía se usan al marcar los múltiplos en ese paso, por ejemplo, para los múltiplos de 3 es 3 × 3 = 9 , 3 × 5 = 15 , 3 × 7 = 21 , 3 × 9 = 27 , ..., 3 × 15 = 45 , ..., por lo que se debe tener cuidado al tratar con esto.
Ver también
Referencias
enlaces externos
- primesieve - Tamiz segmentado C / C ++ muy rápido y altamente optimizado de Eratóstenes
- Eratóstenes, tamiz de en Enciclopedia de Matemáticas
- Página de JavaScript interactiva
- Tamiz de Eratóstenes por George Beck, Wolfram Demonstrations Project .
- Tamiz de Eratóstenes en Haskell
- Se ilustra y explica el algoritmo del Tamiz de Eratóstenes. Implementaciones Java y C ++.
- Un tamiz relacionado escrito en lenguaje ensamblador x86
- Tamiz segmentado CUDA altamente paralelo optimizado rápido de Eratosthenes en C
- Página wiki de SieveOfEratosthenesInManyProgrammingLanguages c2
- El arte del primer tamiz de cribado de Eratosthenes en C de 1998 con buenas características y trucos algorítmicos explicados.