En matemáticas , la criba de Eratóstenes es un antiguo algoritmo para encontrar todos los números primos hasta cualquier 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 primo dado se generan como una secuencia de números a partir de ese primo, con diferencia constante entre ellos que sea igual a ese primo. [1] Esta es la distinción clave del tamiz del uso de la división de prueba para probar secuencialmente la divisibilidad de cada número candidato por cada primo. [2] Una vez que todos los múltiplos de cada primo descubierto se han marcado como compuestos, los números restantes sin marcar son primos.
La referencia más antigua conocida al tamiz ( griego antiguo : κόσκινον Ἐρατοσθένους , kóskinon Eratosthénous ) se encuentra en la Introducción a la aritmética de Nicómaco de Gerasa , [3] de principios del siglo II. Libro CE que lo atribuye a Eratóstenes de Cirene , un siglo III. Matemático griego a. C. , aunque describe el tamizado mediante números impares en lugar de primos. [4]
Uno de varios tamices 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 . [5]
Tamizar los dos y tamizar los tres:
el tamiz de Eratóstenes.
Cuando los múltiplos se subliman,
los números que quedan son primos.
Anónimo [6]
Un número primo es un número natural que tiene exactamente dos divisores naturales distintos : el número 1 y él mismo.
Para encontrar todos los números primos menores o iguales a un entero dado n mediante el método de Eratóstenes:
La idea principal aquí es que todo valor dado a p será primo, porque si fuera compuesto se marcaría como múltiplo de algún otro primo más pequeño. Tenga en cuenta que algunos de los números pueden marcarse más de una vez (por ejemplo, 15 se marcará tanto para 3 como para 5).
Como aclaración, basta con marcar los números en el paso 3 a partir de p 2 , ya que todos los múltiplos más pequeños de p ya habrán sido marcados en ese punto. Esto significa que el algoritmo puede terminar en el paso 4 cuando p 2 es mayor que n . [1]
Otra mejora es enumerar inicialmente solo los números impares, (3, 5, ..., n ) , y contar en incrementos de 2 p en el paso 3, marcando así solo los múltiplos impares de p . En realidad, esto aparece en el algoritmo original. [1] [4] Esto se puede generalizar con factorización de rueda , formando la lista inicial sólo a partir de números coprimos con los primeros primos y no sólo a partir de probabilidades (es decir, números coprimos con 2), y contando en los incrementos correspondientemente ajustados para que En primer lugar, sólo se generan múltiplos de p que son coprimos con esos primos pequeños. [7]
Para encontrar todos los números primos menores o iguales a 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; tache cada segundo número de la lista después del 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 el 3; tacha cada tercer número de la lista después del 3 contando desde 3 en incrementos de 3 (estos serán todos los múltiplos de 3 de la lista):
2 3456789101112131415161718192021222324252627282930
El siguiente número aún no tachado en la lista después del 3 es el 5; tache cada quinto número de la lista después del 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 el 7; el siguiente paso sería tachar cada séptimo número de la lista después del 7, pero ya están todos tachados en este punto, ya que estos números (14, 21, 28) también son múltiplos de primos más pequeños porque 7 × 7 es mayor inferior a 30. Los números no tachados en este punto de la lista son todos los números primos inferiores a 30:
2 3 5 7 11 13 17 19 23 29
La criba de Eratóstenes se puede expresar en pseudocódigo , de la siguiente manera: [8] [9]
algoritmo Tamiz de Eratóstenes es entrada : un número entero n > 1. salida : todos los números primos del 2 al n . sea A una matriz de valores booleanos , indexados por números enteros s 2 an , inicialmente todo configurado en verdadero . para i = 2 , 3, 4, ..., sin exceder √ n si A [ i ] es cierto para j = i 2 , i 2 + i , i 2 +2 i , i 2 +3 i , .. ., sin exceder n, establezca A [ j ] := false devuelve todo i tal que A [ i ] sea verdadero .
Este algoritmo produce todos los números primos no mayores que n . Incluye una optimización común, que consiste en 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 ) , [9] siempre que la actualización de la matriz sea una operación O (1) , como suele ser el caso.
Como señala Sorenson, el problema del tamiz de Eratóstenes no es el número de operaciones que realiza sino más bien sus necesidades de memoria. [9] Para n grande , 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 todo el conjunto A , sin mostrar casi ninguna localidad de referencia .
Una solución a estos problemas la ofrecen los tamices segmentados , en los que sólo se tamizan porciones de la gama a la vez. [10] Estos se conocen desde la década de 1970 y funcionan de la siguiente manera: [9] [11]
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. [9]
Para rangos con un límite superior n tan grande que el tamizado de números primos por debajo de √ n como lo requiere el tamiz segmentado de páginas de Eratóstenes no cabe en la memoria, se puede usar en su lugar un tamiz más lento pero mucho más eficiente en cuanto a espacio, como el tamiz de Sorenson. [12]
Una formulación incremental del tamiz [2] genera números primos indefinidamente (es decir, sin un límite superior) intercalando la generación de números primos con la generación de sus múltiplos (de modo que los números primos se puedan encontrar en espacios entre los múltiplos), donde los múltiplos de cada primo p se genera directamente contando desde el cuadrado del primo en incrementos de p (o 2 p para primos impares). La generación debe iniciarse sólo cuando se alcanza el cuadrado primo, para evitar efectos adversos sobre la eficiencia. Se puede expresar simbólicamente bajo el paradigma del flujo de datos como
primos = [ 2 , 3 , ... ] \ [[ p ², p ²+ p , ...] para p en primos ],
usar 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 por primos secuenciales, un primo a la vez. No es el tamiz de Eratóstenes, pero a menudo se confunde con él, aunque el tamiz de Eratóstenes genera directamente los compuestos en lugar de probarlos. La división de prueba tiene peor complejidad teórica que la del tamiz de Eratóstenes a la hora de generar rangos de números primos. [2]
Al probar cada primo, el algoritmo de división de prueba óptimo utiliza todos los números primos que no exceden su raíz cuadrada, mientras que el tamiz de Eratóstenes produce cada compuesto sólo a partir de sus factores primos y obtiene los primos "gratis" entre los compuestos. El ampliamente conocido código de tamiz funcional de 1975 de David Turner [13] se presenta a menudo como un ejemplo del tamiz de Eratóstenes [7] pero en realidad es un tamiz de división de prueba subóptimo. [2]
El tamiz de Eratóstenes es una forma popular de comparar el rendimiento de una computadora. [14] La complejidad temporal de calcular todos los números primos por debajo de n en el modelo de máquina de acceso aleatorio es O ( n log log n ) , una consecuencia directa del hecho de que la serie de armónicos primos se aproxima asintóticamente a log log n . Sin embargo, tiene una complejidad temporal 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 ) . [15]
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 (√ norte/iniciar sesión sustantivo, masculino—) .
Una versión segmentada especial (rara vez implementada) del tamiz de Eratóstenes, con optimizaciones básicas, utiliza operaciones O ( n ) y O ( √ nregistro registro sustantivo, masculino—/iniciar sesión sustantivo, masculino—) bits de memoria.[16][17][18]
El uso de la notación O grande ignora factores constantes y compensaciones que pueden ser muy importantes para rangos prácticos: el tamiz de la variación de Eratóstenes conocido como tamiz de rueda de Pritchard [16] [17] [18] tiene un rendimiento O ( n ) , pero su implementación básica requiere un algoritmo de "una matriz grande" que limita su rango utilizable a la cantidad de memoria disponible; de lo contrario, es necesario segmentar la página para reducir el uso de memoria. Cuando se implementa con segmentación de páginas para ahorrar memoria, el algoritmo básico aún requiere aproximadamente O (norte/iniciar sesión sustantivo, masculino—) bits de memoria (mucho más que el requisito del tamiz segmentado de páginas básico de Eratóstenes usando O (√ norte/iniciar sesión sustantivo, masculino—) 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 tiene un 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.
La prueba de Euler de la fórmula del producto zeta contiene una versión del tamiz de Eratóstenes en la que cada número compuesto se elimina exactamente una vez. [9] Gries y Misra (1978) redescubrieron el mismo tamiz y observaron que tomaba un tiempo lineal . [19] 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 por cada elemento de la lista (comenzando así por sí mismo) y los resultados se marcan en la lista para su posterior eliminación. A continuación se eliminan de la secuencia de trabajo el elemento inicial y los elementos marcados 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 a partir de 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á sólo números coprimos con los primeros k primos (cf. factorización por rueda ), de modo que la lista comenzará con el siguiente primo, y todos los números que estén debajo del cuadrado de su primer elemento también serán primos.
Por lo tanto, al generar una secuencia acotada de números primos, cuando el siguiente número primo identificado excede la raíz cuadrada del límite superior, todos los números restantes en la lista son primos. [9] En el ejemplo anterior, eso se logra al identificar 11 como el siguiente primo, lo que da una lista de todos los primos menores o iguales a 80.
Tenga en cuenta que los números que se descartarán en un paso aún se utilizan 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 esto. [9]
primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]