Tamiz de atkin

La criba de Atkin es un algoritmo para encontrar todos los números primos hasta un número entero N dado. El algoritmo fue creado por A. O. L. Atkiny D. Yu. Bernstein[1] [2] . La velocidad asintótica del algoritmo declarada por los autorescorresponde a la velocidad de los mejores algoritmos de tamizado conocidos anteriormente, pero en comparación con ellos, el tamiz de Atkin requiere menos memoria.

Descripción

La idea principal del algoritmo es utilizar formas cuadráticas irreducibles (representación de números como ax 2 + by 2 ). Los algoritmos anteriores eran básicamente diversas modificaciones de la criba de Eratóstenes , que utilizaba la representación de números en forma de formas reducidas (normalmente en forma de producto xy ).

De forma simplificada, el algoritmo se puede representar de la siguiente manera:

Todos los números que son ( módulo 60) 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56 o 58 son divisibles por 2 y, por lo tanto, ciertamente no son primos. Todos los números iguales (módulo 60) a 3, 9, 15, 21, 27, 33, 39, 45, 51 o 57 son divisibles por 3 y tampoco son primos. Todos los números iguales (módulo 60) a 5, 25, 35 o 55 son divisibles por 5 y tampoco son primos. Todos estos restos (módulo 60) se ignoran.
- Todos los números que son (módulo 60) 1, 13, 17, 29, 37, 41, 49 o 53 tienen un resto de 1 cuando se dividen por 4. Estos números son primos si y solo si el número de soluciones de la ecuación es 4 x 2 + y 2 = n es impar y el número en sí no es un múltiplo de ningún cuadrado primo ( en:entero sin cuadrados ).
- Los números que son (módulo 60) 7, 19, 31 o 43 tienen un resto de 1 cuando se dividen por 6. Estos números son primos si y solo si el número de soluciones de la ecuación 3 x 2 + y 2 = n es impar y el número en sí no es múltiplo de ningún cuadrado de un número primo.
- Los números que son (módulo 60) 11, 23, 47 o 59 tienen un resto de 11 cuando se dividen por 12. Estos números son primos si y solo si el número de soluciones de la ecuación 3 x 2 − y 2 = n (para x > y ) es impar y el número n en sí mismo no es un múltiplo de ningún cuadrado de un número primo.
- Un paso separado del algoritmo tacha los números que son múltiplos de los cuadrados de los números primos. Dado que ninguno de los números en consideración es divisible por 2, 3 o 5, tampoco son divisibles por sus cuadrados. Por lo tanto, comprobar que un número no es múltiplo del cuadrado de un primo no incluye 2 2 , 3 2 y 5 2 .

Segmentación

Para reducir los requisitos de memoria, el "tamizado" se realiza en porciones (segmentos, bloques), cuyo tamaño es de aproximadamente . ${\ sqrt N}$

Preselección

Para acelerar las cosas, el algoritmo ignora todos los números que son múltiplos de uno de los primeros números primos (2, 3, 5, 7, ...). Esto se hace utilizando estructuras de datos estándar y algoritmos de procesamiento de datos propuestos anteriormente por Paul Pritchard [3 ] . Se les conoce con el nombre en inglés. tamizado de ruedas . El número de primeros primos se elige en función del número dado N. Teóricamente, se propone llevar los primeros primos aproximadamente hasta . Esto nos permite mejorar la estimación asintótica de la velocidad del algoritmo por el factor . En este caso, se requiere memoria adicional que, a medida que crece N, se limita como . El aumento en los requisitos de memoria se estima en . ${\sqrt {\log N))$ ${\displaystyle \mahop {O} {\grande (}1/(\log \log N){\grande )))$ ${\ estilo de visualización \ exp {\ sqrt {\ registro N))}$ ${\displaystyle \mahop {O} {\grande (}N^{\mahop {o} (1)}{\grande)))$

La versión presentada en el sitio web de uno de los autores [4] está optimizada para buscar todos los números primos hasta mil millones ( ), y los números que son múltiplos de 2, 3, 5 y 7 están excluidos de los cálculos (2 × 3 × 5 × 7 = 210). ${\sqrt {\log 10^{9}}}\approx {\sqrt {\log 2^{30}}}={\sqrt {30}}\approx 5{,}5$

Grado de dificultad

Según los autores de [2] , el algoritmo tiene una complejidad asintótica y requiere bits de memoria. Anteriormente, se conocían algoritmos que eran igual de rápidos asintóticamente, pero que requerían mucha más memoria [5] [6] . En teoría, este algoritmo combina la velocidad máxima con los requisitos de memoria más bajos. La implementación del algoritmo, realizada por uno de los autores, muestra una velocidad práctica bastante alta [4] . ${\displaystyle \mahop {O} {\grande (}N/(\log \log N){\grande )))$ ${\displaystyle \mahop {O} {\Grande (}N^{{\frac {1}{2}}+\mahop {o} (1)}{\Grande)))$

El algoritmo utiliza dos tipos de optimización, que aumentan significativamente su eficiencia (en comparación con la versión simplificada).

A continuación se muestra una implementación de una versión simplificada en el lenguaje de programación C , que ilustra la idea principal del algoritmo: el uso de formas cuadráticas:

límite int = 1000 ; int sqr_lim ; bool es_principal [ 1001 ]; int x2 , y2 ; int i , j ; intn ; _ // Inicialización del tamiz sqr_lim = ( int ) sqrt (( long double ) limit ); para ( i = 0 ; i <= límite ; ++ i ) es_primo [ i ] = falso ; es_primo [ 2 ] = verdadero ; es_primo [ 3 ] = verdadero ; // Presumiblemente, los primos son números enteros con un número impar // de representaciones en las formas cuadradas dadas. // x2 e y2 son i y j cuadrados (optimización). x2 = 0 ; para ( yo = 1 ; yo <= sqr_lim ; ++ yo ) { x2 += 2 * i - 1 ; y2 = 0 ; para ( j = 1 ; j <= sqr_lim ; ++ j ) { y2 += 2 * j - 1 ; n = 4 * x2 + y2 ; si (( n <= límite ) && ( n % 12 == 1 || n % 12 == 5 )) es_primo [ n ] = ! es_primo [ n ]; // n = 3 * x2 + y2; n- = x2 ; // Optimización si (( n <= límite ) && ( n % 12 == 7 )) es_primo [ n ] = ! es_primo [ n ]; // n = 3 * x2 - y2; n -= 2 * y2 ; // Optimización si (( i > j ) && ( n <= límite ) && ( n % 12 == 11 )) es_primo [ n ] = ! es_primo [ n ]; } } // Eliminar múltiplos de los cuadrados de números primos en el intervalo [5, sqrt(limit)]. // (el escenario principal no puede eliminarlos) for ( i = 5 ; i <= sqr_lim ; ++ i ) { si ( es_primo [ yo ]) { n = yo * yo ; para ( j = n ; j <= límite ; j += n ) es_primo [ j ] = falso ; } } // Imprime una lista de números primos en la consola. imprimirf ( "2, 3, 5" ); for ( i = 6 ; i <= limit ; ++ i ) { // Se ha añadido la comprobación de la divisibilidad entre 3 y 5. No es necesario en la versión original del algoritmo. if (( es_primo [ i ]) && ( i % 3 != 0 ) && ( i % 5 != 0 )) printf ( ", %d" , i ); }

Versión Pascal del algoritmo

programando ; _ var is_prime : array [ 1 .. 10001 ] of boolean ; jj : int64 ; dosieve de procedimiento ( límite : int64 ) ; var i , k , x , y : int64 ; n : int64 ; empezar por i := 5 para limitar do is_prime [ i ] := false ; for x := 1 to trunc ( sqrt ( limit )) do for y := 1 to trunc ( sqrt ( limit )) do begin n := 4 * sqr ( x ) + sqr ( y ) ; si ( n <= límite ) y (( n mod 12 = 1 ) o ( n mod 12 = 5 )) entonces is_prime [ n ] := not is_prime [ n ] ; n := n - sqr ( x ) ; si ( n <= límite ) y ( n mod 12 = 7 ) entonces es_primo [ n ] := no es_primo [ n ] ; n := n - 2 * sqr ( y ) ; si ( x > y ) y ( n <= límite ) y ( n mod 12 = 11 ) entonces es_primo [ n ] := no es_primo [ n ] ; fin ; for i := 5 to trunc ( sqrt ( limit )) comience si is_prime [ i ] luego comience k : = sqr ( i ) ; norte := k ; while n <= limit do begin is_prime [ n ] := false ; norte := norte + k ; fin ; fin ; fin ; es_primo [ 2 ] := verdadero ; es_primo [ 3 ] := verdadero ; fin ; empezar dosieve ( 10000 ) ; for jj := 1 to 10000 do if is_prime [ jj ] luego writeln ( jj ) ; fin _

Véase también

Enlaces

↑ A. O. L. Atkin, D. J. Bernstein, Prime sieves usando formas cuadráticas binarias Archivado el 3 de febrero de 2007 en Wayback Machine ( 1999).
↑ 1 2 A. O. L. Atkin, D. J. Bernstein, Prime sieves usando formas cuadráticas binarias , Matemáticas. compensación 73 (2004), 1023-1030.
↑ Pritchard, Paul. Explicando el tamiz de ruedas // Acta Informatica. - 1982. - vol. 17 _ - Pág. 477-485 .
↑ 1 2 D. J. Bernstein. primegen (1997). Fecha de acceso: 26 de septiembre de 2010. Archivado desde el original el 27 de abril de 2011. (indefinido)
↑ Paul Pritchard. Tamices de números primos incrementales mejorados . - Springer-Verlag, 1994. - P. 280-288 .
↑ Brain Dunten, Julie Jones, Jonathan Sorenson. Un tamiz de números primos rápidos y eficientes en el espacio // Letras de procesamiento de información. - 1996. - No. 59 . - Pág. 79-84 .