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. [1] 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. [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 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 , [3] a principios del siglo II. Libro de la CE, que lo describe y lo atribuye a Eratóstenes de Cirene , un siglo III. 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 . [4]
Descripción general
el tamiz de Eratóstenes.
Cuando los múltiplos sublimes,
los números que quedan son primos.
Anónimo [5]
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.
- Enumere los múltiplos de p contando en incrementos de p desde 2 p hasta n , y márquelos en la lista (estos serán 2 p , 3 p , 4 p , ... ; la p en sí no debe estar marcada).
- 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 . [1]
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. [1] 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 primos y no solo de probabilidades (es decir, números coprime con 2), y contando en los incrementos ajustados correspondientemente para que solo esos múltiplos de p se generan que son coprime con esos pequeños primos, en primer lugar. [6]
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 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 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 , como sigue: [7] [8]
El algoritmo Sieve of Eratosthenes es de entrada : un número entero n > 1. salida : todos los números primos de 2 a n . dejar que A sea un array de booleanos valores, indexada por número entero s 2 a n , inicialmente todo ajustado a verdadero . para i = 2, 3, 4, ..., sin exceder √ n hacer si A [ i ] es verdadera para j = i 2 , i 2 + i , i 2 +2 i , i 2 +3 i , .. ., sin exceder n do A [ j ]: = falso 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 es comenzar a enumerar los múltiplos de cada primo i de i 2 . La complejidad de tiempo de este algoritmo es O ( n log log n ) , [8] 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. [8] Para n grande , es posible que el rango de primos no quepa en la memoria; lo que es peor, 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. [9] Estos se conocen desde la década de 1970 y funcionan de la siguiente manera: [8] [10]
- 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. [8]
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áginas 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 . [11]
Tamiz incremental
Una formulación incremental del tamiz [2] 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 pueden 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 solo cuando se alcanza el cuadrado principal, para evitar efectos adversos sobre la eficiencia. Puede expresarse simbólicamente bajo el paradigma del flujo de datos como
primos = [ 2 , 3 , ...] \ [[ p ², p ² + p , ...] para p en primos ],
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 mediante el tamizado iterativo de 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. [2]
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 [12] se presenta a menudo como un ejemplo del tamiz de Eratosthenes [6], pero en realidad es un tamiz de división de prueba subóptimo. [2]
Análisis computacional
El trabajo realizado por este algoritmo es casi en su totalidad las operaciones para eliminar las representaciones de números compuestos que para la versión básica no optimizada es la suma del rango dividido por cada uno de los primos hasta ese rango o
donde n es el rango de tamizado en este y todos los análisis posteriores.
Al reorganizar el segundo teorema de Mertens , esto es igual an (log log n + M ) cuando n se acerca al infinito, donde M es la constante de Meissel-Mertens de aproximadamente0,261 49 ...
La optimización de comenzar en el cuadrado de cada primo y descartar solo los primos menores que la raíz cuadrada cambia la " n " en la expresión anterior a √ n (o n1/2) y no sacrificar hasta el cuadrado significa que la suma de los primos básicos cada menos dos se resta de las operaciones. Como la suma de los primeros x primos es1/2x 2 log x [13] y el teorema de los números primos dice que x es aproximadamenteX/log x, entonces la suma de los números primos an esn 2/2 log n, y por lo tanto, la suma de los primos base a √ n es1/log nexpresado como un factor de n . El desplazamiento adicional de dos por prima base es 2 π ( √ n ) , donde π es la función de conteo de primos en este caso, o4 √ n/log n; expresando esto como un factor de n como son los otros términos, esto es4/√ n log n. Combinando todo esto, la expresión para el número de operaciones optimizadas sin factorización de rueda es
Para los casos de factorización de la rueda, hay una compensación adicional de las operaciones no realizadas de
donde x es el número primo de rueda más alto y se aplica un factor constante de toda la expresión, que es la fracción de candidatos primos restantes en comparación con la circunferencia de rueda repetida. La circunferencia de la rueda es
y se puede determinar fácilmente que este factor de rueda es
como p - 1/pages la fracción de candidatos restantes para el primo de rueda más alto, x , y cada primo más pequeño subsiguiente deja su fracción correspondiente de la fracción combinada anterior.
Combinando todo el análisis anterior, el número total de operaciones para un rango de tamizado hasta n, incluida la factorización de la rueda para primos hasta x, es aproximadamente
- .
Para mostrar que la expresión anterior es una buena aproximación al número de operaciones de selección de números compuestos realizadas por el algoritmo, a continuación se muestra una tabla que muestra el número de operaciones realmente medido para una implementación práctica del tamiz de Eratóstenes en comparación con el número de operaciones. predicho a partir de la expresión anterior con ambos expresados como una fracción del rango (redondeado a cuatro lugares decimales) para diferentes rangos de tamizado y factorizaciones de rueda (tenga en cuenta que la última columna es una rueda práctica máxima en cuanto al tamaño de los espacios de rueda Consulte la tabla - casi 10 millones de valores):
norte sin rueda impares 2/3/5 rueda 2/3/5/7 rueda 2/3/5/7/11/13/17/19 rueda 10 3 1,4090 1.3745 0.4510 0,4372 0,1000 0.0909 0.0580 0.0453 0,0060 - 10 4 1,6962 1,6844 0.5972 0.5922 0,1764 0,1736 0.1176 0.1161 0.0473 0.0391 10 5 1,9299 1.9261 0,7148 0,7130 0.2388 0.2381 0.1719 0,1714 0.0799 0.0805 10 6 2.1218 2.1220 0,8109 0.8110 0.2902 0.2903 0.2161 0.2162 0.1134 0,1140 10 7 2.2850 2.2863 0.8925 0.8932 0.3337 0.3341 0.2534 0.2538 0,1419 0.1421 10 8 2.4257 2.4276 0.9628 0.9638 0.3713 0.3718 0.2856 0.2860 0,1660 0.1662
La tabla anterior muestra que la expresión anterior es una muy buena aproximación al número total de operaciones de selección para rangos de tamices de aproximadamente cien mil (10 5 ) y más.
Complejidad algorítmica
El tamiz de Eratóstenes es una forma popular de comparar el rendimiento de la computadora. [14] Como se puede ver en lo anterior, al eliminar todas las compensaciones constantes y los factores constantes e ignorar los términos que tienden a cero cuando n se acerca al infinito, la complejidad temporal de calcular todos los 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 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 ) . [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 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. [16] [17] [18]
Para mostrar que la aproximación anterior en complejidad no es muy precisa incluso para un rango tan grande como práctico, la siguiente es una tabla del número estimado de operaciones como una fracción del rango redondeado a cuatro lugares, la razón calculada para un factor de diez cambios en el rango basado en esta estimación, y el factor basado en la estimación de log log n para varios rangos y factorizaciones de rueda (la columna combinada usa un pre-sacrificio de uso frecuente y práctico por la factorización máxima de rueda pero solo el 2/3 / Rueda 5/7 para el factor rueda, ya que la factorización completa es difícil de implementar de manera eficiente para la segmentación de páginas):
norte sin rueda impares 2/3/5 rueda 2/3/5/7 rueda rueda combinada 2/3/5/7/11/13/17/19 rueda 10 6 2.122 1.102 1.075 0,811 1,137 1.075 0.2903 1,22 1.075 0.2162 1.261 1.075 0.1524 1.416 1.075 0,114 1.416 1.075 10 7 2.2863 1.077 1.059 0.8932 1.101 1.059 0.3341 1,151 1.059 0.2537 1,174 1.059 0,1899 1.246 1.059 0.1421 1.246 1.059 10 8 2.4276 1.062 1.048 0.9638 1.079 1.048 0.3718 1,113 1.048 0,286 1.127 1.048 0.2222 1,17 1.048 0.1662 1,17 1.048 10 9 2.5514 1.051 1.04 1.0257 1.064 1.04 0.4048 1.089 1.04 0.3143 1.099 1.04 0.2505 1.127 1.04 0.1874 1.127 1.04 10 10 2,6615 1.043 1.035 1.0808 1.054 1.035 0.4342 1.073 1.035 0.3395 1.08 1.035 0.2757 1.101 1.035 0,2063 1.101 1.035 10 11 2.7608 1.037 1.03 1.1304 1.046 1.03 0.4607 1.061 1.03 0.3622 1.067 1.03 0.2984 1.082 1.03 0.2232 1.082 1.03 10 12 2.8511 1.033 1.027 1.1755 1.04 1.027 0.4847 1.052 1.027 0.3828 1.057 1.027 0,319 1.069 1.027 0.2387 1.069 1.027 10 13 2.9339 1.029 1.024 1.217 1.035 1.024 0.5068 1.046 1.024 0.4018 1.049 1.024 0.3379 1.059 1.024 0,2528 1.059 1.024 10 14 3.0104 1.026 1.022 1.2552 1.031 1.022 0.5272 1.04 1.022 0.4193 1.044 1.022 0.3554 1.052 1.022 0.2659 1.052 1.022 10 15 3.0815 1.024 1.02 1.2907 1.028 1.02 0.5462 1.036 1.02 0.4355 1.039 1.02 0.3717 1.046 1.02 0.2781 1.046 1.02 10 16 3.1478 1.022 1.018 1.3239 1.026 1.018 0.5639 1.032 1.018 0.4507 1.035 1.018 0.3868 1.041 1.018 0.2894 1.041 1.018
Lo anterior muestra que la estimación de log log n no es muy precisa incluso para rangos prácticos máximos de aproximadamente 10 16 . Uno puede ver por qué no coincide al observar el análisis computacional anterior y ver que dentro de estos límites prácticos del rango de tamizado, hay términos de compensación constante muy significativos, de modo que el término log n de crecimiento muy lento no se vuelve lo suficientemente grande como para Haga que estos términos sean insignificantes hasta que el rango de tamizado se acerque al infinito, mucho más allá de cualquier rango de tamizado práctico. Dentro de estos rangos prácticos, estas compensaciones constantes significativas significan que el rendimiento del tamiz de Eratóstenes es mucho mejor de lo que cabría esperar con solo usar las estimaciones de complejidad de tiempo asintótico en una cantidad significativa, pero eso también significa que la pendiente del rendimiento con rango creciente es más pronunciado de lo previsto, ya que el beneficio de las compensaciones constantes se vuelve ligeramente menos significativo.
También se debe tener en cuenta que al usar las relaciones de operación calculadas para el rango del tamiz, debe ser inferior a aproximadamente 0,2587 para ser más rápido que el tamiz de Atkin que se compara a menudo si las operaciones toman aproximadamente el mismo tiempo cada una en los ciclos de reloj de la CPU, lo que es una suposición razonable para el algoritmo de matriz de un bit enorme. Usando esa suposición, el tamiz de Atkin es solo más rápido que el tamiz factorizado de rueda máxima de Eratóstenes para rangos de más de 10 13, momento en el que la enorme matriz de búfer de tamiz necesitaría aproximadamente un cuarto de terabyte (aproximadamente 250 gigabytes) de memoria RAM incluso si se utilizó empaquetadura de bits. Un análisis de las versiones segmentadas de páginas mostrará que la suposición de que el tiempo por operación permanece igual entre los dos algoritmos no es válido para la segmentación de páginas y que el tamiz de las operaciones de Atkin se vuelve más lento mucho más rápido que el tamiz de Eratóstenes con rango creciente. Por lo tanto, para fines prácticos, el tamiz de Eratóstenes con factorización máxima de la rueda es más rápido que el tamiz de Atkin, aunque el tamiz de Atkin es más rápido para cantidades menores de factorización de la rueda.
El uso de la notación O grande tampoco es la forma correcta de comparar el rendimiento práctico de variaciones uniformes del Tamiz de Eratóstenes, ya que ignora factores constantes y compensaciones que pueden ser muy importantes para rangos prácticos: La variación del tamiz de Eratóstenes conocida como el 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, necesita segmentar la página para reducir la memoria. usar. 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 al límite como se describe arriba de la tabla, pero el costo es un factor constante bastante grande de aproximadamente tres en el tiempo de ejecución a aproximadamente tres cuartas partes del rango del tamiz debido a los complejos cálculos necesarios para hacerlo. Como se puede ver en la tabla anterior para el tamiz básico de Eratóstenes, aunque el tamiz de rueda resultante tieneun rendimiento O ( n )y un requisito de memoria aceptable, nunca será más rápido que un tamiz básico de Eratóstenes razonablemente factorizado por rueda para cualquier práctica. rango de tamizado por un factor de aproximadamente dos. Aparte de eso, es bastante complejo de implementar, rara vez se implementa en la práctica porque todavía usa más memoria que las implementaciones básicas de Sieve of Eratosthenes descritas aquí, además de ser más lento para rangos prácticos. Por tanto, es más una curiosidad intelectual que algo práctico.
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. [8] El mismo tamiz fue redescubierto y observó a tomar tiempo lineal por Gries y Misra (1978) . [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 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. Así, 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 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. [8] 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. [8]
Ver también
- Tamiz de Sundaram
- Tamiz de Atkin
- Teoría del tamiz
Referencias
- ^ a b c Horsley, Rev. Samuel, FRS, " Κόσκινον Ερατοσθένους o, The Sieve of Eratosthenes. Siendo un relato de su método para encontrar todos los números primos," Philosophical Transactions (1683-1775), vol. 62. (1772), págs. 327–347 .
- ^ a b c d O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes" , Journal of Functional Programming , publicado en línea por Cambridge University Press el 9 de octubre de 2008 doi : 10.1017 / S0956796808007004 , págs. 10, 11 (contiene dos tamices en Haskell: uno basado en cola de prioridad de O'Neill y uno basado en lista, de Richard Bird).
- ^ Hoche, Richard , ed. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II , Leipzig: BG Teubner, p. 31
- ^ JC Morehead, "Extensión del tamiz de Eratóstenes a progresiones y aplicaciones aritméticas", Annals of Mathematics, Segunda serie 10 : 2 (1909), págs. 88-104 .
- ^ Clocksin, William F., Christopher S. Mellish, Programación en Prolog , 1984, p. 170. ISBN 3-540-11046-1 .
- ^ a b Runciman, Colin (1997). "Perla funcional: cribas de rueda perezosa y espirales de primes" (PDF) . Revista de programación funcional . 7 (2): 219–225. doi : 10.1017 / S0956796897002670 .
- ^ Sedgewick, Robert (1992). Algoritmos en C ++ . Addison-Wesley. ISBN 978-0-201-51059-1., pag. dieciséis.
- ^ a b c d e f g h Jonathan Sorenson, Introducción a los tamices de números primos , Informe técnico de Ciencias de la Computación # 909, Departamento de Ciencias de la Computación de la Universidad de Wisconsin-Madison, 2 de enero de 1990 (el uso de la optimización de partir de cuadrados, y, por lo tanto, se muestran solo los números cuyo cuadrado está por debajo del límite superior).
- ^ Crandall & Pomerance, Prime Numbers: A Computational Perspective , segunda edición, Springer: 2005, págs. 121-24.
- ^ Bays, Carter; Hudson, Richard H. (1977). "El tamiz segmentado de Eratóstenes y primos en progresiones aritméticas a 10 12 ". BIT . 17 (2): 121-127. doi : 10.1007 / BF01932283 . S2CID 122592488 .
- ^ J. Sorenson, "El tamiz principal de pseudocuadrados" , Actas del 7º Simposio Internacional sobre Teoría Algorítmica de Números . (ANTS-VII, 2006).
- ^ Turner, manual de idioma de David A. SASL. Tech. rept. CS / 75/1. Departamento de Ciencias Computacionales, Universidad de St. Andrews 1975. (). Pero véase también Peter Henderson, Morris, James Jr., un perezoso Evaluador de 1976 , en la que encontramos la siguiente , que se atribuye a P. Quarendon:; la prioridad no está clara.
primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0
primeswrt[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]]
- ^ E. Bach y J. Shallit, §2.7 en Teoría algorítmica de números , vol. 1: Algoritmos eficientes, MIT Press, Cambridge, MA, 1996.
- ^ Peng, TA (otoño de 1985). "Un millón de primos a través del tamiz" . BYTE . págs. 243–244 . Consultado el 19 de marzo de 2016 .
- ^ Pritchard, Paul, "Tamices lineales de números primos: un árbol genealógico", Sci. Computación. Programming 9 : 1 (1987), págs. 17–35.
- ^ a b Paul Pritchard, "Un tamiz aditivo sublineal para encontrar números primos", Comunicaciones del ACM 24 (1981), 18-23. SEÑOR600730
- ↑ a b Paul Pritchard, Explicación del tamiz de rueda, Acta Informatica 17 (1982), 477–485. SEÑOR685983
- ↑ a b Paul Pritchard, "Tamices de números primos compactos rápidos" (entre otros), Journal of Algorithms 4 (1983), 332-344. SEÑOR729229
- ^ Gries, David ; Misra, Jayadev (diciembre de 1978), "Un algoritmo de tamiz lineal para encontrar números primos" (PDF) , Comunicaciones del ACM , 21 (12): 999–1003, doi : 10.1145 / 359657.359660 , hdl : 1813/6407 , S2CID 11990373.
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.