Atkinovo síto

Atkinovo síto je algoritmus pro nalezení všech prvočísel až do daného celého čísla N. Algoritmus vytvořil A. O. L. Atkina D. Yu Bernstein[1] [2] . Asymptotická rychlost algoritmu deklarovaná autoryodpovídá rychlosti nejznámějších dříve známých sítovacích algoritmů, ale ve srovnání s nimi vyžaduje Atkinovo síto méně paměti.

Popis

Hlavní myšlenkou algoritmu je použití neredukovatelných kvadratických forem (reprezentace čísel jako ax 2 + x 2 ). Předchozí algoritmy byly v podstatě různé modifikace Eratosthenova síta , které využívaly reprezentaci čísel ve formě redukovaných forem (obvykle ve formě součinu xy ).

Ve zjednodušené formě může být algoritmus reprezentován následovně:

Všechna čísla, která jsou ( 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 nebo 58 jsou dělitelná 2, a proto rozhodně nejsou prvočísla. Všechna čísla rovna (modulo 60) až 3, 9, 15, 21, 27, 33, 39, 45, 51 nebo 57 jsou dělitelná 3 a také nejsou prvočísla. Všechna čísla rovna (modulo 60) až 5, 25, 35 nebo 55 jsou dělitelná 5 a také nejsou prvočísla. Všechny tyto zbytky (modulo 60) jsou ignorovány.
- Všechna čísla, která jsou (modulo 60) 1, 13, 17, 29, 37, 41, 49 nebo 53, mají při dělení 4 zbytek 1. Tato čísla jsou prvočísla právě tehdy, když je počet řešení rovnice 4 x 2 + y 2 = n je liché a samotné číslo není násobkem žádného prvočísla ( en:čtverec bez celého čísla ).
- Čísla, která jsou (modulo 60) 7, 19, 31 nebo 43, mají při dělení 6 zbytek 1. Tato čísla jsou prvočísla právě tehdy, když je počet řešení rovnice 3 x 2 + y 2 = n lichý a samotné číslo není násobkem žádné druhé mocniny prvočísla.
- Čísla, která jsou (modulo 60) 11, 23, 47 nebo 59, mají po dělení 12 zbytek 11. Tato čísla jsou prvočísla právě tehdy, když počet řešení rovnice 3 x 2 − y 2 = n ( např. x > y ) je liché a samotné číslo n není násobkem žádné druhé mocniny prvočísla.
- Samostatný krok algoritmu škrtne čísla, která jsou násobky druhých mocnin prvočísel. Protože žádné z uvažovaných čísel není dělitelné 2, 3 nebo 5, nejsou tedy dělitelná ani svými čtverci. Proto kontrola, že číslo není násobkem druhé mocniny prvočísla, nezahrnuje 2 2 , 3 2 a 5 2 .

Segmentace

Pro snížení nároků na paměť se „prosévání“ provádí po částech (segmentech, blocích), jejichž velikost je přibližně . ${\sqrt N}$

Prescreening

Aby se to urychlilo, algoritmus ignoruje všechna čísla, která jsou násobky jednoho z prvních několika prvočísel (2, 3, 5, 7, ...). To se provádí pomocí standardních datových struktur a algoritmů pro zpracování dat navržených dříve Paulem Pritchardem [3 ] . Jsou známé pod anglickým názvem. kolo prosévání . Počet prvočísel se volí v závislosti na daném počtu N. Teoreticky se navrhuje brát první prvočísla přibližně do . To nám umožňuje zlepšit asymptotický odhad rychlosti algoritmu o faktor . V tomto případě je vyžadována další paměť, která je s rostoucím N omezena jako . Nárůst požadavků na paměť se odhaduje jako . ${\sqrt {\log N))$ ${\displaystyle \mathop {O} {\big (}1/(\log \log N){\big )))$ $\exp {\sqrt {\log N))$ ${\displaystyle \mathop {O} {\big (}N^{\mathop {o} (1)}{\big )))$

Verze prezentovaná na webu jednoho z autorů [4] je optimalizována pro vyhledávání všech prvočísel do miliardy ( ), z výpočtů jsou vyloučena čísla, která jsou násobky 2, 3, 5 a 7 (2 × 3 × 5 × 7 = 210). ${\sqrt {\log 10^{9}}}\přibližně {\sqrt {\log 2^{30}}}={\sqrt {30}}\přibližně 5{,}5$

Hodnocení obtížnosti

Podle autorů [2] má algoritmus asymptotickou složitost a vyžaduje bity paměti. Dříve byly známy algoritmy, které byly stejně asymptoticky rychlé, ale vyžadovaly podstatně více paměti [5] [6] . Teoreticky tento algoritmus kombinuje maximální rychlost s nejnižšími požadavky na paměť. Implementace algoritmu, provedená jedním z autorů, vykazuje poměrně vysokou praktickou rychlost [4] . ${\displaystyle \mathop {O} {\big (}N/(\log \log N){\big )))$ ${\displaystyle \mathop {O} {\Big (}N^{{\frac {1}{2}}+\mathop {o} (1)}{\Big )))$

Algoritmus využívá dva typy optimalizace, které výrazně zvyšují jeho efektivitu (oproti zjednodušené verzi).

Níže je implementace zjednodušené verze v programovacím jazyce C , která ilustruje hlavní myšlenku algoritmu - použití kvadratických forem:

int limit = 1000 ; int sqr_lim ; bool je_prvočíslo [ 1001 ]; int x2 , y2 ; int i , j ; int n ; // Inicializace síta sqr_lim = ( int ) sqrt (( long double ) limit ); pro ( i = 0 ; i <= limit ; +++ i ) is_prime [ i ] = false ; is_prime [ 2 ] = true ; is_prime [ 3 ] = true ; // Pravděpodobně prvočísla jsou celá čísla s lichým počtem // zobrazení v daných čtvercových tvarech. // x2 a y2 jsou i a j čtverce (optimalizace). x2 = 0 ; for ( i = 1 ; i <= sqr_lim ; ++ i ) { x2 += 2 * i - 1 ; y2 = 0 ; for ( j = 1 ; j <= sqr_lim ; ++ j ) { y2 += 2 * j - 1 ; n = 4 * x2 + y2 ; if (( n <= limit ) && ( n % 12 == 1 || n % 12 == 5 )) is_prime [ n ] = ! je_prvočíslo [ n ]; // n = 3 * x2 + y2; n- = x2 ; // Optimalizace if (( n <= limit ) && ( n % 12 == 7 )) is_prime [ n ] = ! je_prvočíslo [ n ]; // n = 3 * x2 - y2; n- = 2 * y2 ; // Optimalizace if (( i > j ) && ( n <= limit ) && ( n % 12 == 11 )) is_prime [ n ] = ! je_prvočíslo [ n ]; } } // Vyřazení násobků druhých mocnin prvočísel v intervalu [5, sqrt(limit)]. // (hlavní scéna je nemůže vyřadit) for ( i = 5 ; i <= sqr_lim ; ++ i ) { if ( is_prime [ i ]) { n = i * i ; pro ( j = n ; j <= limit ; j += n ) is_prime [ j ] = false ; } } // Tisk seznamu prvočísel do konzole. printf ( "2, 3, 5" ); for ( i = 6 ; i <= limit ; ++ i ) { // byla přidána kontrola dělitelnosti 3 a 5. V původní verzi algoritmu to není potřeba. if (( is_prime [ i ]) && ( i % 3 != 0 ) && ( i % 5 != 0 )) printf ( ", %d" , i ); }

Pascal verze algoritmu

programatkin ; _ var is_prime : array [ 1 .. 10001 ] of boolean ; jj : int64 ; postup dosieve ( limit : int64 ) ; var i , k , x , y : int64 ; n : int64 ; begin for 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 ) ; if ( n <= limit ) a (( n mod 12 = 1 ) nebo ( n mod 12 = 5 )) then is_prime [ n ] := not is_prime [ n ] ; n := n - sqr ( x ) ; if ( n <= limit ) and ( n mod 12 = 7 ) then is_prime [ n ] := not is_prime [ n ] ; n := n - 2 * sqr ( y ) ; if ( x > y ) and ( n <= limit ) and ( n mod 12 = 11 ) then is_prime [ n ] := not is_prime [ n ] ; konec ; for i := 5 to trunc ( sqrt ( limit )) do begin if is_prime [ i ] then begin k := sqr ( i ) ; n := k ; while n <= limit do begin is_prime [ n ] := false ; n := n + k ; konec ; konec ; konec ; is_prime [ 2 ] := true ; is_prime [ 3 ] := true ; konec ; začátek dávky ( 10 000 ) ; for jj := 1 až 10000 do if is_prime [ jj ] then writeln ( jj ) ; konec .

Viz také

Odkazy

↑ A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms Archived 3 February 2007 at the Wayback Machine ( 1999).
↑ 1 2 A. O. L. Atkin, D. J. Bernstein, Prime síta pomocí binárních kvadratických forem , Math. Comp. 73 (2004), 1023-1030.
↑ Pritchard, Paul. Vysvětlení kolového síta // Acta Informatica. - 1982. - Sv. 17 . - str. 477-485 .
↑ 1 2 D. J. Bernstein. primegen (1997). Datum přístupu: 26. září 2010. Archivováno z originálu 27. dubna 2011. (neurčitý)
↑ Paul Pritchard. Vylepšená síta s přírůstkovými prvočísly . - Springer-Verlag, 1994. - S. 280-288 .
↑ Brain Dunten, Julie Jones, Jonathan Sorenson. Prostorově efektivní rychlé síto prvočísel // Informační zpracování dopisů. - 1996. - Ne. 59 . - str. 79-84 .