Sita lui Atkin

Sita lui Atkin este un algoritm pentru găsirea tuturor numerelor prime până la un număr întreg dat N. Algoritmul a fost creat de A. O. L. Atkinși D. Yu. Bernstein[1] [2] . Viteza asimptotică a algoritmului declarată de autoricorespunde vitezei celor mai bine cunoscuți algoritmi de cernere, dar în comparație cu aceștia, sita Atkin necesită mai puțină memorie.

Descriere

Ideea principală a algoritmului este de a folosi forme pătratice ireductibile (reprezentarea numerelor ca ax 2 + cu 2 ). Algoritmii anteriori erau practic diverse modificări ale site-ului lui Eratosthenes , care foloseau reprezentarea numerelor sub formă de forme reduse (de obicei sub forma unui produs xy ).

Într-o formă simplificată, algoritmul poate fi reprezentat după cum urmează:

Toate numerele care sunt ( modulo 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 sau 58 sunt divizibili cu 2 și, prin urmare, cu siguranță nu sunt primii. Toate numerele egale (modul 60) cu 3, 9, 15, 21, 27, 33, 39, 45, 51 sau 57 sunt divizibile cu 3 și, de asemenea, nu sunt prime. Toate numerele egale (modul 60) cu 5, 25, 35 sau 55 sunt divizibile cu 5 și, de asemenea, nu sunt prime. Toate aceste resturi (modulo 60) sunt ignorate.
- Toate numerele care sunt (modulo 60) 1, 13, 17, 29, 37, 41, 49 sau 53 au un rest de 1 când sunt împărțite la 4. Aceste numere sunt prime dacă și numai dacă numărul de soluții ale ecuației este 4 x 2 + y 2 = n este impar și numărul în sine nu este un multiplu al niciunui pătrat prim ( en:square-free integer ).
- Numerele care sunt (modulo 60) 7, 19, 31 sau 43 au un rest de 1 atunci când sunt împărțite la 6. Aceste numere sunt prime dacă și numai dacă numărul de soluții ale ecuației 3 x 2 + y 2 = n este impar iar numărul în sine nu este un multiplu al vreunui pătrat al unui prim.
- Numerele care sunt (modulo 60) 11, 23, 47 sau 59 au un rest de 11 atunci când sunt împărțite la 12. Aceste numere sunt prime dacă și numai dacă numărul de soluții ale ecuației 3 x 2 − y 2 = n (pentru x > y ) este impar și numărul n în sine nu este un multiplu al niciunui pătrat al unui prim.
- Un pas separat al algoritmului taie numerele care sunt multipli ai pătratelor primelor. Deoarece niciunul dintre numerele luate în considerare nu este divizibil cu 2, 3 sau 5, atunci, în consecință, ele nu sunt divizibile nici prin pătratele lor. Prin urmare, verificarea faptului că un număr nu este un multiplu al pătratului unui prim nu include 2 2 , 3 2 și 5 2 .

Segmentare

Pentru a reduce cerințele de memorie, „cernerea” se realizează în porțiuni (segmente, blocuri), a căror dimensiune este de aproximativ . ${\sqrt N}$

Prescreening

Pentru a accelera lucrurile, algoritmul ignoră toate numerele care sunt multiple ale unuia dintre primele câteva numere prime (2, 3, 5, 7, ...). Acest lucru se realizează prin utilizarea structurilor de date standard și a algoritmilor de procesare a datelor propuși anterior de Paul Pritchard [3 ] . Ele sunt cunoscute sub numele englezesc. cernerea rotii . Numărul primelor prime este ales în funcție de numărul dat N. Teoretic, se propune ca primele numere prime aproximativ până la . Acest lucru ne permite să îmbunătățim estimarea asimptotică a vitezei algoritmului cu un factor . În acest caz, este necesară o memorie suplimentară, care, pe măsură ce N crește, este mărginită ca . Creșterea cerințelor de memorie este estimată ca . ${\sqrt {\log N}}$ $\mathop {O} {\big (}1/(\log \log N){\big ))$ $\exp {\sqrt {\log N}}$ $\mathop {O} {\big (}N^{\mathop {o} (1)}{\big ))$

Versiunea prezentată pe site-ul unuia dintre autori [4] este optimizată pentru căutarea tuturor numerelor prime de până la un miliard ( ), iar numerele care sunt multipli de 2, 3, 5 și 7 sunt excluse din calcule (2 × 3 × 5 × 7 = 210). ${\sqrt {\log 10^{9}}}\aprox {\sqrt {\log 2^{30}}}={\sqrt {30}}\aprox 5{,}5$

Evaluare de dificultate

Potrivit autorilor din [2] , algoritmul are complexitate asimptotică și necesită biți de memorie. Anterior, se știau algoritmi care erau la fel de rapidi asimptotic, dar necesită mult mai multă memorie [5] [6] . Teoretic, acest algoritm combină viteza maximă cu cele mai mici cerințe de memorie. Implementarea algoritmului, realizată de unul dintre autori, arată o viteză practică destul de mare [4] . $\mathop {O} {\big (}N/(\log \log N) {\big ))$ $\mathop {O} {\Big (}N^{{\frac {1}{2}}+\mathop {o} (1)}{\Big ))$

Algoritmul folosește două tipuri de optimizare, care îi sporesc semnificativ eficiența (comparativ cu versiunea simplificată).

Mai jos este o implementare a unei versiuni simplificate în limbajul de programare C , ilustrând ideea principală a algoritmului - utilizarea formelor pătratice:

int limit = 1000 ; int sqr_lim ; bool este_prim [ 1001 ]; int x2 , y2 ; int i , j ; int n ; // Sieve initialization sqr_lim = ( int ) sqrt (( long double ) limit ); pentru ( i = 0 ; i <= limită ; ++ i ) is_prim [ i ] = fals ; este_prim [ 2 ] = adevărat ; este_prim [ 3 ] = adevărat ; // Probabil că primele sunt numere întregi cu un număr impar // de reprezentări în formele pătrate date. // x2 și y2 sunt pătrate i și j (optimizare). x2 = 0 ; pentru ( i = 1 ; i <= sqr_lim ; ++ i ) { x2 += 2 * i - 1 ; y2 = 0 ; pentru ( j = 1 ; j <= sqr_lim ; ++ j ) { y2 += 2 * j - 1 ; n = 4 * x2 + y2 ; dacă (( n <= limită ) && ( n % 12 == 1 || n % 12 == 5 )) este_prim [ n ] = ! este_prim [ n ]; // n = 3 * x2 + y2; n -= x2 ; // Optimizare dacă (( n <= limită ) && ( n % 12 == 7 )) este_prim [ n ] = ! este_prim [ n ]; // n = 3 * x2 - y2; n -= 2 * y2 ; // Optimizare dacă (( i > j ) && ( n <= limită ) && ( n % 12 == 11 )) este_prim [ n ] = ! este_prim [ n ]; } } // Îndepărtează multiplii pătratelor primelor în intervalul [5, sqrt(limit)]. // (scena principală nu le poate elimina) pentru ( i = 5 ; i <= sqr_lim ; ++ i ) { dacă ( este_prim [ i ]) { n = i * i ; pentru ( j = n ; j <= limită ; j += n ) is_prim [ j ] = fals ; } } // Imprimă o listă de numere prime pe consolă. printf ( "2, 3, 5" ); pentru ( i = 6 ; i <= limită ; ++ i ) { // a fost adăugată verificarea divizibilității cu 3 și 5. Nu este nevoie de aceasta în versiunea originală a algoritmului. dacă (( este_prim [ i ]) && ( i % 3 != 0 ) && ( i % 5 != 0 )) printf ( ", %d" , i ); }

Versiunea Pascal a algoritmului

programatkin ; _ var is_prime : matrice [ 1 .. 10001 ] de boolean ; jj : int64 ; doza de procedura ( limita : int64 ) ; var i , k , x , y : int64 ; n : int64 ; începe pentru i := 5 to limit 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 ) ; dacă ( n <= limită ) și (( n mod 12 = 1 ) sau ( n mod 12 = 5 )) atunci este_prim [ n ] := nu este_prim [ n ] ; n := n - sqr ( x ) ; dacă ( n <= limită ) și ( n mod 12 = 7 ) atunci este_prim [ n ] := nu este_prim [ n ] ; n := n - 2 * sqr ( y ) ; dacă ( x > y ) și ( n <= limită ) și ( n mod 12 = 11 ) atunci este_prim [ n ] := nu este_prim [ n ] ; sfârşitul ; for i := 5 to trunc ( sqrt ( limit )) do begin if is_prime [ i ] then begin k := sqr ( i ) ; n := k ; în timp ce n <= limit do begin is_prime [ n ] := false ; n := n + k ; sfârşitul ; sfârşitul ; sfârşitul ; este_prim [ 2 ] := adevărat ; este_prim [ 3 ] := adevărat ; sfârşitul ; începe doza ( 10000 ) ; pentru jj := 1 la 10000 do if is_prime [ jj ] atunci scriețiln ( jj ) ; sfârşitul .

Vezi și

Link -uri

↑ A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms Arhivat la 3 februarie 2007 la Wayback Machine ( 1999).
↑ 1 2 A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms , Math. Comp. 73 (2004), 1023-1030.
↑ Pritchard, Paul. Explicarea site-ului de roată // Acta Informatică. - 1982. - Vol. 17 . - P. 477-485 .
↑ 1 2 D. J. Bernstein. primegen (1997). Data accesului: 26 septembrie 2010. Arhivat din original la 27 aprilie 2011. (nedefinit)
↑ Paul Pritchard. Site îmbunătățite pentru numărul prim incremental . - Springer-Verlag, 1994. - P. 280-288 .
↑ Brain Dunten, Julie Jones, Jonathan Sorenson. O sită rapidă cu numere prime eficiente în spațiu // Scrisori de procesare a informațiilor. - 1996. - Nr. 59 . - P. 79-84 .