Tamiz de Eratóstenes

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Sieve of Eratosthenes: pasos de algoritmo para los primos inferiores a 121 (incluyendo la optimización de partir de la plaza de primo).

En matemáticas, la tamiz de Eratóstenes es un algoritmo antiguo para encontrar todos los números primos hasta cualquier límite dado.

Lo hace marcando iterativamente como compuestos (es decir, no primos) los múltiplos de cada número 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 con ese número primo, con diferencia constante entre ellos que es igual a ese primo. Esta es la distinción clave de la criba del uso de la división de prueba para probar secuencialmente la divisibilidad de cada número candidato por cada número primo. 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) está en Nicómaco de Gerasa Introducción a la aritmética, una primera del siglo II. Libro CE que lo atribuye a Eratóstenes de Cirene, un siglo III. BCE Matemático griego, aunque describe el tamizado por números impares en lugar de números primos.

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.

Resumen

Sift the Two's y Sift the Three's:
La Sieve de Eratosthenes.
Cuando los múltiplos sublimes,
Los números que quedan son Prime.

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 dado $n$ de Eratóstenes' método:

Crear una lista de enteros consecutivos de 2 a $n$ : $(2, 3, 4,... n)$ .
Inicialmente, déjalo $p$ igual 2, el número primario más pequeño.
Enumerar los múltiplos de $p$ contando en incrementos de $p$ desde $2 p$ a $n$ , y marcarlos en la lista (esto será $2 p, 3 p, 4 p,...$ ; el $p$ en sí mismo no debe ser marcado).
Encontrar el número más pequeño en la lista mayor que $p$ Eso no está marcado. Si no hubiera tal número, basta. De lo contrario, déjalo $p$ ahora iguala a este nuevo número (que es el próximo primero), y repite del paso 3.
Cuando el algoritmo termina, los números restantes no marcados en la lista son todos los primeros abajo $n$ .

La idea principal aquí es que cada valor dado a $p$ será primo, porque si fuera compuesto estaría marcado como un 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 (p. ej., 15 se marcará tanto para el 3 como para el 5).

Como refinamiento, es suficiente 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 se habrán marcado en ese punto. Esto significa que el algoritmo puede terminar en el paso 4 cuando $p 2$ es mayor que $n$ .

Otro refinamiento es listar inicialmente solo números impares, $(3, 5,..., n)$ , y contar en incrementos de < span class="texhtml">2p en el paso 3, marcando así solo múltiplos impares de $p$ . Esto realmente 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 coprimos con los primeros primos y no solo de probabilidades (es decir, números coprimos con 2), y contando en los incrementos ajustados correspondientemente para que solo tales múltiplos de $p$ que son coprimos con esos primos pequeños, en primer lugar.

Ejemplo

Para encontrar todos los números primos menores o iguales a 30, proceda de la siguiente manera.

Primero, genera una lista de números enteros del 2 al 30:

2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 24 25 27 28 29

El primer número de la lista es 2; tache 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 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 siguiente número en la lista después del 2 es el 3; tache 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 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 siguiente número que aún no se ha tachado en la lista después del 3 es el 5; tache cada quinto número en la lista después de 5 contando hacia arriba desde 5 en incrementos de 5 (es decir, todos los múltiplos de 5):

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 siguiente número que aún no se ha tachado en la lista después del 5 es el 7; el siguiente paso sería tachar cada 7 números 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 de 30. Los números no 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

La criba de Eratóstenes se puede expresar en pseudocódigo, de la siguiente manera:

algoritmo Sieve of Eratosthenes es entrada: un entero n ■ 1.
 Producto: todos los números primos de 2 a n.

 Deja A ser un array de Boolean valores, indexados por enteros 2 a n,
inicialmente todo set a verdadero.

 para i = 2, 3, 4,...  $\sqrt n$  do si A[i] es verdadero para j = i², i²+i, i²+2i, i²+3i,... no excede n do set A[j# falso retorno Todos i tales que A[i] es verdadero.

Este algoritmo produce todos los primos no mayores que $n$ . Incluye una optimización común, que consiste en comenzar a enumerar los múltiplos de cada número primo $i$ de $< i>i 2$ . La complejidad temporal de este algoritmo es $O (n log log n)$ , siempre que la actualización de matriz es 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 el número de operaciones que realiza, sino sus requisitos de memoria. Para grandes $n$ , el rango de números primos puede no caber en la memoria; peor aún, incluso para $n$ moderados, 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 porciones de la gama a la vez. Estos se conocen desde la década de 1970 y funcionan de la siguiente manera:

Divide el rango 2 a $n$ en segmentos de algún tamaño $Δ \leq \sqrt n$ .
Encuentre los primos en el primer segmento (es decir, el más bajo), utilizando el tamiz regular.
Para cada uno de los siguientes segmentos, en orden creciente, con m siendo el valor más alto del segmento, encontrar los primeros en él como sigue:
1. Configurar una matriz booleana de tamaño $Δ$ , y
2. Marcar como no-prime las posiciones en el array correspondiente a los múltiplos de cada primo $p \leq \sqrt m$ encontrado hasta ahora, enumerando sus múltiples pasos de $p$ desde el múltiplo más bajo $p$ entre $m - Δ$ y $m$ . Las posiciones restantes corresponden a los primeros en el segmento. No es necesario procesar los principios encontrados en el segmento actual, porque todos ellos son más grandes que $\sqrt m$ . (Para) $k \geq 1$ , uno tiene ${displaystyle (kDelta +1)}{2}(k+1)Delta }$ .)

Si se elige $Δ$ para que sea $\sqrt n$ , la complejidad espacial del algoritmo es $O (\sqrt n)< /span>, mientras que la complejidad del tiempo es la misma que la del tamiz normal.$

Para rangos con límite superior $n$ tan grande que el tamizado prima debajo de $\sqrt n$ según lo requiera el tamiz segmentado de la página de Eratóstenes no puede caber en la memoria, en su lugar 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 de la criba genera números primos indefinidamente (es decir, sin un límite superior) al intercalar la generación de números primos con la generación de sus múltiplos (para que los números primos se puedan encontrar en los 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 de la prima, para evitar efectos adversos en la eficiencia. Se puede expresar simbólicamente bajo el paradigma del flujo de datos como

primos =2, 3[p2, p2+pPara... p dentro primos]

utilizando la notación de comprensión de lista con que denota la resta de conjuntos de progresiones aritméticas de números.

Los primos también se pueden producir tamizando iterativamente 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, aunque el tamiz de Eratóstenes 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 números primos.

Al probar cada número primo, el algoritmo de división de prueba óptimo usa 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 números primos &# 34;gratis", entre los compuestos. El ampliamente conocido código de tamiz funcional de 1975 de David Turner a menudo se presenta 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 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 aproxima asintóticamente a $registrar registro n$ . Sin embargo, tiene una complejidad de tiempo exponencial con respecto al tamaño de entrada, lo que lo convierte en un algoritmo pseudo-polinomio. 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 la página normalmente implementada tiene la misma complejidad operativa de $O (n log log n)$ como la versión no segmentada, pero reduce los requisitos de espacio al tamaño mínimo de la página del segmento más la memoria requerida para almacenar los números primos base menos que la raíz cuadrada del rango utilizado para seleccionar compuestos de segmentos de página sucesivos de tamaño $O (\sqrt n / log n)$ .

Una versión segmentada especial (rara vez, si alguna vez, implementada) del tamiz de Eratóstenes, con optimizaciones básicas, usa $O (n)$ operaciones y $O (\sqrt n registro registro n / registro n)$ bits de memoria.

Usar la notación O grande ignora los factores constantes y las compensaciones que pueden ser muy significativas para los rangos prácticos: la variación de la criba de Eratóstenes conocida como criba de rueda de Pritchard tiene una $O (n)$ rendimiento, pero su implementación básica requiere una "una matriz grande" algoritmo que limita su rango utilizable a la cantidad de memoria disponible; de lo contrario, debe segmentarse por página para reducir el uso de memoria. Cuando se implementa con la segmentación de páginas para ahorrar memoria, el algoritmo básico aún requiere aproximadamente $O (n / log n)$ bits de memoria (mucho más que el requisito de la página básica del tamiz segmentado de Eratóstenes usando $O (\sqrt n < /span> / 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 tiene un rendimiento O (n) y un requisito de memoria aceptable, no es más rápido que un razonablemente Rueda tamiz básico factorizado de Eratóstenes para rangos prácticos de tamizado.$

Tamiz de Euler

La prueba de Euler de la fórmula del producto zeta contiene una versión del tamiz de Eratóstenes en el que cada número compuesto se elimina exactamente una vez. El mismo tamiz fue redescubierto y observado para tomar tiempo lineal por Gries & 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 número primo, se multiplica con cada elemento de la lista (empezando así por sí mismo) y los resultados se marcan en la lista para su posterior eliminación. A continuació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 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 cuotas, 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 coprimos con el primer $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, al generar una secuencia acotada de números primos, cuando el siguiente número primo identificado supera la raíz cuadrada del límite superior, todos los números restantes de la lista son primos. En el ejemplo dado arriba, eso se logra al identificar 11 como siguiente primo, dando 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 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.

Contenido relacionado

Más resultados...