Atkins si

Atkins si er en algoritme til at finde alle primtal op til et givet heltal N. Algoritmen blev skabt af A. O. L. Atkinog D. Yu. Bernstein[1] [2] . Den asymptotiske hastighed af den algoritme , som forfatterne har erklæret,svarer til hastigheden af de bedst kendte sigtealgoritmer, men i sammenligning med dem kræver Atkin-sien mindre hukommelse.

Beskrivelse

Hovedideen med algoritmen er at bruge irreducible kvadratiske former (repræsentation af tal som akse 2 + med 2 ). De tidligere algoritmer var dybest set forskellige modifikationer af sigten af Eratosthenes , som brugte repræsentationen af tal i form af reducerede former (normalt i form af et produkt xy ).

I en forenklet form kan algoritmen repræsenteres som følger:

Alle tal, der er ( 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 eller 58 er delelige med 2 og er derfor bestemt ikke primtal. Alle tal lig (modulo 60) med 3, 9, 15, 21, 27, 33, 39, 45, 51 eller 57 er delelige med 3 og er heller ikke primtal. Alle tal lig (modulo 60) med 5, 25, 35 eller 55 er delelige med 5 og er heller ikke primtal. Alle disse rester (modulo 60) ignoreres.
- Alle tal, der er (modulo 60) 1, 13, 17, 29, 37, 41, 49 eller 53, har en rest på 1, når de divideres med 4. Disse tal er prime, hvis og kun hvis antallet af løsninger af ligningen er 4 x 2 + y 2 = n er ulige, og selve tallet er ikke et multiplum af et primtal kvadrat ( en:kvadratfrit heltal ).
- Tal, der er (modulo 60) 7, 19, 31 eller 43, har en rest på 1, når de divideres med 6. Disse tal er prime, hvis og kun hvis antallet af løsninger af ligningen 3 x 2 + y 2 = n er ulige og selve tallet er ikke et multiplum af et hvilket som helst kvadrat af et primtal.
- Tal, der er (modulo 60) 11, 23, 47 eller 59, har en rest på 11, når de divideres med 12. Disse tal er prime, hvis og kun hvis antallet af løsninger af ligningen 3 x 2 − y 2 = n (for x > y ) er ulige, og selve tallet n er ikke et multiplum af et hvilket som helst kvadrat af et primtal.
- Et separat trin i algoritmen overstreger tal, der er multipla af primtals kvadrater. Da ingen af de tal, der tages i betragtning, er delelige med 2, 3 eller 5, er de derfor heller ikke delelige med deres kvadrater. Derfor, at kontrollere, at et tal ikke er et multiplum af kvadratet af et primtal, inkluderer ikke 2 2 , 3 2 og 5 2 .

Segmentering

For at reducere hukommelseskravene udføres "sifting" i portioner (segmenter, blokke), hvis størrelse er ca. ${\sqrt N}$

Prescreening

For at fremskynde tingene ignorerer algoritmen alle tal, der er multipla af et af de første par primtal (2, 3, 5, 7, ...). Dette gøres ved at bruge standard datastrukturer og databehandlingsalgoritmer foreslået tidligere af Paul Pritchard [3 ] . De er kendt under det engelske navn. hjulsigtning . Antallet af første primtal vælges afhængigt af det givne tal N. Teoretisk foreslås det at tage de første primtal cirka op til . Dette giver os mulighed for at forbedre det asymptotiske estimat af algoritmens hastighed med faktoren . I dette tilfælde kræves der yderligere hukommelse, som, når N vokser, er afgrænset som . Stigningen i hukommelsesbehov anslås til . ${\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 )))$

Den version, der præsenteres på en af forfatternes websted [4] er optimeret til at søge efter alle primtal op til en milliard ( ), og tal, der er multipla af 2, 3, 5 og 7, er udelukket fra beregninger (2 × 3 × 5 × 7 = 210). ${\sqrt {\log 10^{9}}}\approx {\sqrt {\log 2^{30}}}={\sqrt {30}}\approx 5{,}5$

Sværhedsgrad

Ifølge forfatterne af [2] har algoritmen asymptotisk kompleksitet og kræver stykker hukommelse. Tidligere kendte man algoritmer, der var lige så asymptotisk hurtige, men som kræver væsentlig mere hukommelse [5] [6] . Teoretisk kombinerer denne algoritme den maksimale hastighed med de laveste hukommelseskrav. Implementeringen af algoritmen, udført af en af forfatterne, viser en ret høj praktisk hastighed [4] . ${\displaystyle \mathop {O} {\big (}N/(\log \log N){\big )))$ ${\displaystyle \mathop {O} {\Big (}N^{{\frac {1}{2}}+\mathop {o} (1)}{\Big )))$

Algoritmen bruger to typer optimering, som øger effektiviteten markant (sammenlignet med den forenklede version).

Nedenfor er en implementering af en forenklet version i programmeringssproget C , der illustrerer algoritmens hovedidé - brugen af kvadratiske former:

int grænse = 1000 ; int sqr_lim ; bool er_prime [ 1001 ]; int x2 , y2 ; int i , j ; int n ; // Sieve initialisering sqr_lim = ( int ) sqrt (( lang dobbelt ) grænse ); for ( i = 0 ; i <= grænse ; ++ i ) is_prime [ i ] = falsk ; is_prime [ 2 ] = sand ; is_prime [ 3 ] = sand ; // Formodentlig er primtal heltal med et ulige antal // af repræsentationer i de givne kvadratiske former. // x2 og y2 er i og j kvadrater (optimering). 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 ; hvis (( n <= grænse ) && ( n % 12 == 1 || n % 12 == 5 )) is_prime [ n ] = ! er_primtal [ n ]; // n = 3 * x2 + y2; n- = x2 ; // Optimering hvis (( n <= grænse ) && ( n % 12 == 7 )) is_prime [ n ] = ! er_primtal [ n ]; //n = 3 * x2 - y2; n- = 2 * y2 ; // Optimering hvis (( i > j ) && ( n <= grænse ) && ( n % 12 == 11 )) is_prime [ n ] = ! er_primtal [ n ]; } } // Lug multipla af kvadraterne af primtal ud i intervallet [5, sqrt(grænse)]. // (hovedscenen kan ikke luge dem ud) for ( i = 5 ; i <= sqr_lim ; ++ i ) { if ( er_primtal [ i ]) { n = i * i ; for ( j = n ; j <= grænse ; j += n ) is_prime [ j ] = falsk ; } } // Udskriv en liste over primtal til konsollen. printf ( "2, 3, 5" ); for ( i = 6 ; i <= limit ; ++ i ) { // check for delelighed med 3 og 5 er blevet tilføjet. Der er ikke behov for det i den originale version af algoritmen. if (( er_primtal [ i ]) && ( i % 3 != 0 ) && ( i % 5 != 0 )) printf ( ", %d" , i ); }

Pascal version af algoritmen

programatkin ; _ var is_prime : array [ 1 .. 10001 ] af boolean ; jj : int64 ; procedure dosis ( grænse : int64 ) ; var i , k , x , y : int64 ; n : int64 ; start for i := 5 for at begrænse do is_prime [ i ] := falsk ; for x := 1 til trunc ( sqrt ( limit )) gør for y := 1 to trunc ( sqrt ( limit )) do begin n := 4 * sqr ( x ) + sqr ( y ) ; hvis ( n <= grænse ) og (( n mod 12 = 1 ) eller ( n mod 12 = 5 )) så is_prime [ n ] := ikke er_prime [ n ] ; n := n - sqr ( x ) ; hvis ( n <= grænse ) og ( n mod 12 = 7 ) så er_prime [ n ] := ikke er_prime [ n ] ; n := n - 2 * sqr ( y ) ; hvis ( x > y ) og ( n <= grænse ) og ( n mod 12 = 11 ) så er_primtal [ n ] := ikke er_primtal [ n ] ; ende ; for i := 5 for at afkorte ( sqrt ( limit )) begynder hvis is_prime [ i ] så begynder k : = sqr ( i ) ; n := k ; mens n <= grænse begynder er_prime [ n ] : = falsk ; n := n + k ; ende ; ende ; ende ; is_prime [ 2 ] := sand ; is_prime [ 3 ] := sand ; ende ; begynde dosis ( 10000 ) ; for jj := 1 til 10000 gør hvis er_prime [ jj ] så skrivln ( jj ) ; ende .