En matemáticas , la criba de Eratóstenes es un antiguo algoritmo para encontrar todos los números primos hasta un límite dado.
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 comenzando desde ese primo, con una diferencia constante entre ellos que es igual a ese primo. [1] Esta es la distinción clave del tamiz con respecto al uso de la división de prueba para probar secuencialmente cada número candidato para 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 Nicómaco de Gerasa , [3] un libro de principios del siglo II d. C. que lo atribuye a Eratóstenes de Cirene , un matemático griego del siglo III a. C. , aunque describe el tamizado por números impares en lugar de primos. [4]
Uno de los muchos tamices de números primos , es una de las formas más eficientes de encontrar todos los primos más pequeños. Puede usarse para encontrar primos en progresiones aritméticas . [5]
Tamizar los dos y tamizar los tres:
la criba de Eratóstenes.
Cuando los múltiplos 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 cada 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 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 habrán sido marcados en ese punto. Esto significa que el algoritmo puede terminar en el paso 4 cuando p 2 sea mayor que n . [1]
Otro refinamiento es listar 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 . Esto en realidad aparece en el algoritmo original. [1] [4] Esto se puede generalizar con la factorización de rueda , formando la lista inicial solo a partir de números coprimos con los primeros primos y no solo a partir de impares (es decir, números coprimos con 2), y contando en los incrementos ajustados correspondientes de modo que solo se generen los múltiplos de p que son coprimos con esos primos pequeños, en primer lugar. [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; tacha cada segundo número de la lista después del 2 contando hacia arriba 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 del 3 contando hacia arriba desde 3 en incrementos de 3 (estos serán todos los múltiplos de 3 en la lista):
2 3456789101112131415161718192021222324252627282930
El siguiente número que aún no ha sido tachado en la lista después del 3 es el 5; tache cada quinto número en la lista después del 5 contando hacia arriba desde 5 en incrementos de 5 (es decir, todos los múltiplos de 5):
2 3456789101112131415161718192021222324252627282930
El siguiente número que aún no está 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 todos ellos ya están 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 que 30. Los números que no están tachados en este punto de la lista son todos los números primos menores 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]
El algoritmo Criba de Eratóstenes tiene como entrada : un entero n > 1. Salida : todos los números primos del 2 al n . Sea A una matriz de valores booleanos , indexada por el entero s 2 a n , Inicialmente todo configurado como verdadero . para i = 2, 3, 4, ..., sin exceder √ n hacer si A [ i ] es verdadero para j = i 2 , i 2 + i , i 2 +2 i , i 2 +3 i , ..., sin exceder n hacer A [ j ] : = falso devuelve todos los i tales 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 a partir 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 con el tamiz de Eratóstenes no es el número de operaciones que realiza sino más bien sus requisitos de memoria. [9] Para un valor n grande , el rango de primos puede no caber en la memoria; peor aún, incluso para un valor n moderado , su uso de caché es altamente subóptimo. El algoritmo recorre toda la matriz A , sin exhibir casi ninguna localidad de referencia .
Una solución a estos problemas la ofrecen los tamices segmentados , en los que sólo se tamizan porciones del rango 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 límite superior n tan grande que los primos de tamizado por debajo de √ n requeridos por el tamiz segmentado de páginas de Eratóstenes no caben en la memoria, se puede utilizar en su lugar un tamiz más lento pero mucho más eficiente en términos de espacio como el tamiz de primos pseudocuadrados, desarrollado por Jonathan P. Sorenson. [12]
Una formulación incremental del tamiz [2] genera primos indefinidamente (es decir, sin un límite superior) al intercalar la generación de primos con la generación de sus múltiplos (de modo que los primos se puedan encontrar en los huecos entre los múltiplos), donde los múltiplos de cada primo p se generan directamente contando hacia arriba 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 del primo, para evitar efectos adversos en la eficiencia. Puede expresarse simbólicamente bajo el paradigma del flujo de datos como
primos = [ 2 , 3 , ...] \ [[ p ², p ²+ p , ...] para p en primos ],
utilizando notación de comprensión de listas\ para denotar la resta de conjuntos de progresiones aritméticas de números.
Los primos también pueden producirse mediante el tamizado iterativo de los compuestos a través de 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, a pesar de que el tamiz de Eratóstenes genera directamente los compuestos en lugar de realizar pruebas para ellos. La división por tanteo tiene una complejidad teórica peor que la del tamiz de Eratóstenes a la hora de generar rangos de primos. [2]
Al probar cada primo, el algoritmo de división por tanteo óptimo utiliza todos los números primos que no excedan su raíz cuadrada, mientras que la criba 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 criba funcional de 1975 de David Turner [13] se presenta a menudo como un ejemplo de la criba de Eratóstenes [7], pero en realidad es una criba de división por tanteo subóptima. [2]
La criba de Eratóstenes es una forma popular de evaluar el rendimiento de las computadoras. [14] 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 ) operaciones, una consecuencia directa del hecho de que la serie armónica de primos se acerca asintóticamente a log log n . Sin embargo, tiene una complejidad temporal exponencial con respecto a la longitud de la 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 requerida para almacenar los primos base menores que la raíz cuadrada del rango utilizado para seleccionar compuestos de segmentos de página sucesivos de tamaño O ( √n/registro n ) .
Una versión segmentada especial (raramente implementada, si es que alguna vez se implementa) del tamiz de Eratóstenes, con optimizaciones básicas, utiliza operaciones O ( n ) y O ( √ n registro registro n/registro n) bits de memoria. [16] [ 17] [18]
El uso de la notación O grande ignora los factores constantes y los desplazamientos que pueden ser muy significativos para los rangos prácticos: la criba de variación de Eratóstenes conocida como la criba de rueda de Pritchard [16] [17] [18] tiene un rendimiento de O ( n ) , pero su implementación básica requiere un algoritmo de "una gran matriz" que limita su rango utilizable a la cantidad de memoria disponible, de lo contrario, debe segmentarse en páginas 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/registro n) bits de memoria (mucho más que el requerimiento del tamiz segmentado de página básica de Eratóstenes usando O ( √n/registro n) bits de memoria). El trabajo de Pritchard redujo el requerimiento de memoria a costa de un gran factor constante. Aunque el tamiz de rueda resultante tiene un rendimiento de O ( n ) y un requerimiento de memoria aceptable, no es más rápido que un tamiz básico de Eratóstenes con factor de rueda razonable para rangos de tamizado prácticos.
La prueba de Euler de la fórmula del producto zeta contiene una versión de la criba de Eratóstenes en la que cada número compuesto se elimina exactamente una vez. [9] La misma criba fue redescubierta y observada por Gries y Misra (1978) que toma 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 con cada elemento de la lista (empezando por sí mismo) y los resultados se marcan en la lista para su posterior eliminación. Luego, el elemento inicial y los elementos marcados se eliminan de la secuencia de trabajo y el proceso se repite:
[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 partiendo de los números impares, después del primer paso del algoritmo. Así, en el k- ésimo paso se eliminan de la lista todos los múltiplos restantes del k -ésimo primo, que a partir de entonces contendrá solo números coprimos con los primeros k primos (cf. factorización de rueda ), de modo que la lista comenzará con el primo siguiente y todos los números que se encuentren en ella por 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 dado anteriormente, esto se logra al identificar 11 como el siguiente número primo, lo que da una lista de todos los números primos menores o iguales a 80.
Téngase en cuenta que los números que se descartarán en un paso se siguen utilizando 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]]