Atkins såll

Atkins sikt är en algoritm för att hitta alla primtal upp till ett givet heltal N. Algoritmen skapades av A.O.L. Atkinoch D. Yu. Bernstein[1] [2] . Den asymptotiska hastigheten för algoritmen som deklarerats av författarnamotsvarar hastigheten för de mest tidigare kända siktningsalgoritmerna, men i jämförelse med dem kräver Atkin-sikten mindre minne.

Beskrivning

Algoritmens huvudidé är att använda irreducerbara kvadratiska former (representation av tal som axe 2 + med 2 ). De tidigare algoritmerna var i princip olika modifieringar av sikten av Eratosthenes , som använde representationen av tal i form av reducerade former (vanligtvis i form av en produkt xy ).

I en förenklad form kan algoritmen representeras enligt följande:

Alla tal som är ( 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 är delbara med 2 och är därför absolut inte primtal. Alla tal lika (modulo 60) med 3, 9, 15, 21, 27, 33, 39, 45, 51 eller 57 är delbara med 3 och är inte heller primtal. Alla tal lika (modulo 60) med 5, 25, 35 eller 55 är delbara med 5 och är inte heller primtal. Alla dessa rester (modulo 60) ignoreras.
- Alla tal som är (modulo 60) 1, 13, 17, 29, 37, 41, 49 eller 53 har en återstod av 1 när de divideras med 4. Dessa tal är primtal om och endast om antalet lösningar i ekvationen är 4 x 2 + y 2 = n är udda och talet i sig är inte en multipel av någon primkvadrat ( sv:kvadratfritt heltal ).
- Tal som är (modulo 60) 7, 19, 31 eller 43 har en återstod av 1 när de divideras med 6. Dessa tal är primtal om och endast om antalet lösningar av ekvationen 3 x 2 + y 2 = n är udda och talet i sig är inte en multipel av någon kvadrat av ett primtal.
- Tal som är (modulo 60) 11, 23, 47 eller 59 har en återstod av 11 när de divideras med 12. Dessa tal är primtal om och endast om antalet lösningar av ekvationen 3 x 2 − y 2 = n (för x > y ) är udda och talet n i sig är inte en multipel av någon kvadrat i ett primtal.
- Ett separat steg i algoritmen stryker ut tal som är multiplar av kvadraterna av primtal. Eftersom inget av de aktuella talen är delbart med 2, 3 eller 5, är de följaktligen inte heller delbara med sina kvadrater. Att kontrollera att ett tal inte är en multipel av kvadraten av ett primtal inkluderar därför inte 2 2 , 3 2 och 5 2 .

Segmentering

För att minska minneskraven utförs "siktning" i portioner (segment, block), vars storlek är ungefär . ${\sqrt N}$

Prescreening

För att påskynda det hela ignorerar algoritmen alla tal som är multiplar av ett av de första primtal (2, 3, 5, 7, ...). Detta görs genom att använda standarddatastrukturer och databehandlingsalgoritmer som tidigare föreslagits av Paul Pritchard [3 ] . De är kända under det engelska namnet. hjulsiktning . Antalet första primtal väljs beroende på det givna talet N. Teoretiskt föreslås det att de första primtalen tar ungefär upp till . Detta tillåter oss att förbättra den asymptotiska uppskattningen av algoritmens hastighet med faktorn . I detta fall krävs ytterligare minne, som, när N växer, begränsas till . Ökningen av minnesbehov uppskattas till . ${\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 som presenteras på en av författarnas webbplats [4] är optimerad för att söka efter alla primtal upp till en miljard ( ), och tal som är multiplar av 2, 3, 5 och 7 exkluderas från beräkningar (2 × 3 × 5 × 7 = 210). ${\sqrt {\log 10^{9}}}\approx {\sqrt {\log 2^{30}}}={\sqrt {30}}\approx 5{,}5$

Svårighetsgrad

Enligt författarna till [2] har algoritmen asymptotisk komplexitet och kräver minnesbitar . Tidigare var algoritmer kända som var lika asymptotiskt snabba, men som kräver betydligt mer minne [5] [6] . Teoretiskt kombinerar denna algoritm den maximala hastigheten med de lägsta minneskraven. Implementeringen av algoritmen, utförd av en av författarna, visar en ganska hög praktisk hastighet [4] . ${\displaystyle \mathop {O} {\big (}N/(\log \log N){\big )))$ ${\displaystyle \mathop {O} {\Big (}N^{{\frac {1}{2}}+\mathop {o} (1)}{\Big )))$

Algoritmen använder två typer av optimering, vilket avsevärt ökar dess effektivitet (jämfört med den förenklade versionen).

Nedan är en implementering av en förenklad version i programmeringsspråket C , som illustrerar huvudidén med algoritmen - användningen av kvadratiska former:

int limit = 1000 ; int sqr_lim ; bool är_prime [ 1001 ]; int x2 , y2 ; int i , j ; int n ; // Sieve initialisering sqr_lim = ( int ) sqrt (( lång dubbel ) limit ); för ( i = 0 ; i <= gräns ; ++ i ) is_prime [ i ] = falskt ; is_prime [ 2 ] = sant ; is_prime [ 3 ] = sant ; // Förmodligen är primtal heltal med ett udda antal // representationer i de givna kvadratformerna. // x2 och y2 är i och 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 ; om (( n <= gräns ) && ( n % 12 == 1 || n % 12 == 5 )) is_prime [ n ] = ! är_primtal [ n ]; //n = 3 * x2 + y2; n- = x2 ; // Optimering om (( n <= limit ) && ( n % 12 == 7 )) is_prime [ n ] = ! är_primtal [ n ]; //n = 3 * x2 - y2; n- = 2 * y2 ; // Optimering om (( i > j ) && ( n <= limit ) && ( n % 12 == 11 )) is_prime [ n ] = ! är_primtal [ n ]; } } // Sås bort multiplar av kvadraterna av primtal i intervallet [5, sqrt(limit)]. // (huvudstadiet kan inte sålla bort dem) för ( i = 5 ; i <= sqr_lim ; ++ i ) { if ( är_primtal [ i ]) { n = i * i ; för ( j = n ; j <= limit ; j += n ) is_prime [ j ] = falskt ; } } // Skriv ut en lista med primtal till konsolen. printf ( "2, 3, 5" ); for ( i = 6 ; i <= limit ; ++ i ) { // check för delbarhet med 3 och 5 har lagts till. Det finns inget behov av det i den ursprungliga versionen av algoritmen. om (( är_primtal [ i ]) && ( i % 3 != 0 ) && ( i % 5 != 0 )) printf ( ", %d" , i ); }

Pascal-versionen av algoritmen

programatkin ; _ var is_prime : array [ 1 .. 10001 ] av boolean ; jj : int64 ; procedurdos ( gräns : int64 ) ; _ var i , k , x , y : int64 ; n : int64 ; börja för i := 5 för att begränsa do is_prime [ i ] := false ; för x := 1 till trunc ( sqrt ( limit )) gör för y := 1 to trunc ( sqrt ( limit )) börjar n : = 4 * sqr ( x ) + sqr ( y ) ; om ( n <= limit ) och (( n mod 12 = 1 ) eller ( n mod 12 = 5 )) då is_prime [ n ] := not is_prime [ n ] ; n := n - sqr ( x ) ; om ( n <= limit ) och ( n mod 12 = 7 ) så är_prime [ n ] := inte is_prime [ n ] ; n := n - 2 * sqr ( y ) ; om ( x > y ) och ( n <= gräns ) och ( n mod 12 = 11 ) då är_prime [ n ] := inte är_prime [ n ] ; slut ; för i := 5 för att avkorta ( sqrt ( limit )) börja om is_prime [ i ] och sedan börja k := sqr ( i ) ; n := k ; medan n <= limit börjar är_prime [ n ] : = false ; n := n + k ; slut ; slut ; slut ; is_prime [ 2 ] := sant ; is_prime [ 3 ] := sant ; slut ; börja dos ( 10000 ) ; för jj := 1 till 10000 gör om is_prime [ jj ] sedan skrivln ( jj ) ; slut .

Se även

Länkar

↑ A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary square forms Arkiverad 3 februari 2007 på 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. Förklara hjulsilen // Acta Informatica. - 1982. - Vol. 17 . - s. 477-485 .
↑ 1 2 D. J. Bernstein. primegen (1997). Datum för åtkomst: 26 september 2010. Arkiverad från originalet den 27 april 2011. (obestämd)
↑ Paul Pritchard. Förbättrade inkrementella primtalssiktar . - Springer-Verlag, 1994. - P. 280-288 .
↑ Brain Dunten, Julie Jones, Jonathan Sorenson. En rymdeffektiv snabb primtalssikt // Informationsbearbetningsbokstäver. - 1996. - Nej . 59 . - S. 79-84 .