Atkinin seula

Atkinin seula on algoritmi, joka etsii kaikki alkuluvut tiettyyn kokonaislukuun N asti. Algoritmin on luonut A. O. L. Atkinja D. Yu. Bernstein[1] [2] . Kirjoittajien ilmoittama algoritmin asymptoottinen nopeus vastaa tunnetuimpien seulontaalgoritmien nopeutta, mutta niihin verrattuna Atkin-seula vaatii vähemmän muistia.

Kuvaus

Algoritmin pääideana on käyttää redusoitumattomia neliömuotoja (lukujen esitys ax 2 + x 2 :lla ). Aiemmat algoritmit olivat pohjimmiltaan erilaisia Eratosthenesin seulan muunnelmia , joissa käytettiin lukujen esittämistä pelkistetyissä muodoissa (yleensä tuotteen xy muodossa ).

Yksinkertaistetussa muodossa algoritmi voidaan esittää seuraavasti:

Kaikki luvut, jotka ovat ( 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 tai 58 ovat jaollisia kahdella, eivätkä ne siksi todellakaan ole alkulukuja. Kaikki luvut, jotka ovat yhtä suuret (moduuli 60) 3, 9, 15, 21, 27, 33, 39, 45, 51 tai 57, ovat jaollisia kolmella eivätkä myöskään alkulukuja. Kaikki luvut, jotka ovat yhtä suuret (moduuli 60) kuin 5, 25, 35 tai 55, ovat jaollisia 5:llä eivätkä myöskään ole alkulukuja. Kaikki nämä jäännökset (modulo 60) jätetään huomioimatta.
- Kaikissa luvuissa, jotka ovat (moduuli 60) 1, 13, 17, 29, 37, 41, 49 tai 53, jäännös on 1, kun ne jaetaan 4:llä. Nämä luvut ovat alkulukuja, jos ja vain jos yhtälön ratkaisujen määrä on 4 x 2 + y 2 = n on pariton ja itse luku ei ole minkään alkuneliön kerrannainen ( en:neliötön kokonaisluku ).
- Lukujen, jotka ovat (moduuli 60) 7, 19, 31 tai 43, jäännös on 1, kun ne jaetaan 6:lla. Nämä luvut ovat alkulukuja silloin ja vain, jos yhtälön 3 x 2 + y 2 = n ratkaisujen lukumäärä on pariton ja itse luku ei ole alkuluvun minkään neliön kerrannainen.
- Lukujen, jotka ovat (moduuli 60) 11, 23, 47 tai 59, jäännös on 11, kun ne jaetaan 12:lla. Nämä luvut ovat alkulukuja silloin ja vain, jos yhtälön ratkaisujen lukumäärä 3 x 2 − y 2 = n (for x > y ) on pariton eikä itse luku n ole alkuluvun minkään neliön kerrannainen.
- Algoritmin erillinen vaihe ylittää luvut, jotka ovat alkulukujen neliöiden kerrannaisia. Koska mikään tarkasteltavana olevista luvuista ei ole jaollinen 2:lla, 3:lla tai 5:llä, ne eivät siis ole jaollisia neliöillään. Siksi sen tarkistaminen, että luku ei ole alkuluvun neliön kerrannainen, ei sisällä lukuja 2 2 , 3 2 ja 5 2 .

Segmentointi

Muistivaatimusten vähentämiseksi "seulonta" suoritetaan osissa (segmenteissä, lohkoissa), joiden koko on noin . ${\sqrt N}$

Esiesitys

Asian nopeuttamiseksi algoritmi jättää huomioimatta kaikki luvut, jotka ovat muutaman ensimmäisen alkuluvun (2, 3, 5, 7, ...) kerrannaisia. Tämä tehdään käyttämällä vakiotietorakenteita ja tietojenkäsittelyalgoritmeja, joita Paul Pritchard on aiemmin ehdottanut [3 ] . Ne tunnetaan englanninkielisellä nimellä. pyörän seulonta . Ensimmäisten alkulukujen lukumäärä valitaan annetun luvun N mukaan. Teoreettisesti ehdotetaan, että ensimmäiset alkuluvut otetaan suunnilleen arvoon . Näin voimme parantaa algoritmin nopeuden asymptoottista arviota kertoimella . Tässä tapauksessa tarvitaan lisämuistia, joka N:n kasvaessa rajoittuu muotoon . Muistitarpeen kasvun arvioidaan olevan . ${\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 )))$

Yhden kirjoittajan verkkosivustolla [4] esitetty versio on optimoitu etsimään kaikkia alkulukuja miljardiin asti ( ), ja luvut, jotka ovat 2:n, 3:n, 5:n ja 7:n kerrannaisia, on jätetty pois laskelmista (2 × 3 × 5 × 7 = 210). ${\sqrt {\log 10^{9}}}\approx {\sqrt {\log 2^{30}}}={\sqrt {30}}\noin 5{,}5$

Vaikeusaste

[2] : n tekijöiden mukaan algoritmilla on asymptoottinen monimutkaisuus ja se vaatii bittejä muistia. Aikaisemmin tunnettiin algoritmeja, jotka olivat yhtä asymptoottisesti nopeita, mutta vaativat huomattavasti enemmän muistia [5] [6] . Teoriassa tämä algoritmi yhdistää suurimman nopeuden alhaisimpiin muistivaatimuksiin. Algoritmin toteutus, jonka yksi kirjoittajista on suorittanut, osoittaa melko suurta käytännön nopeutta [4] . ${\displaystyle \mathop {O} {\big (}N/(\log \log N){\big )))$ ${\displaystyle \mathop {O} {\Big (}N^{{\frac {1}{2}}+\mathop {o} (1)}{\Big )))$

Algoritmi käyttää kahden tyyppistä optimointia, mikä lisää merkittävästi sen tehokkuutta (verrattuna yksinkertaistettuun versioon).

Alla on yksinkertaistetun version toteutus C -ohjelmointikielellä , joka havainnollistaa algoritmin pääideaa - neliömuotojen käyttöä:

int limit = 1000 ; int sqr_lim ; bool on alkuluku [ 1001 ]; int x2 , y2 ; int i , j ; int n ; // Seulan alustus sqr_lim = ( int ) sqrt (( long double ) limit ); for ( i = 0 ; i <= raja ; ++ i ) on_alkuluku [ i ] = epätosi ; on_alkuluku [ 2 ] = tosi ; on_alkuluku [ 3 ] = tosi ; // Oletettavasti alkuluvut ovat kokonaislukuja, joissa on pariton määrä // esityksiä annetuissa neliömuodoissa. // x2 ja y2 ovat i- ja j-neliöitä (optimointi). 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 <= raja ) && ( n % 12 == 1 || n % 12 == 5 )) on_alkuluku [ n ] = ! on alkuluku [ n ]; // n = 3 * x2 + y2; n = x2 ; // Optimointi jos (( n <= raja ) && ( n % 12 == 7 )) on_alkuluku [ n ] = ! on alkuluku [ n ]; // n = 3 * x2 - y2; n = 2 * y2 ; // Optimointi if (( i > j ) && ( n <= raja ) && ( n % 12 == 11 )) on_alkuluku [ n ] = ! on alkuluku [ n ]; } } // Karsitaan alkulukujen neliöiden kerrannaiset väliltä [5, sqrt(limit)]. // (päävaihe ei voi karsia niitä pois) for ( i = 5 ; i <= sqr_lim ; ++ i ) { if ( on_alkuluku [ i ]) { n = i * i ; for ( j = n ; j <= raja ; j += n ) on_alkuluku [ j ] = epätosi ; } } // Tulosta alkulukuluettelo konsoliin. printf ( "2, 3, 5" ); for ( i = 6 ; i <= limit ; ++ i ) { // jaotettavuus 3:lla ja 5:llä on lisätty. Algoritmin alkuperäisessä versiossa sitä ei tarvita. if (( on_alkuluku [ i ]) && ( i % 3 != 0 ) && ( i % 5 != 0 )) printf ( ", %d" , i ); }

Algoritmin Pascal-versio

ohjelmatkin ; _ var is_prime : taulukko [ 1 .. 10001 ] boolen arvosta ; jj : int64 ; menettely dosieve ( raja : int64 ) ; var i , k , x , y : int64 ; n : int64 ; aloita i : = 5 rajaan do is_prime [ i ] : = false ; for x := 1 katkaisee ( sqrt ( raja )) do for y := 1 katkaisee ( sqrt ( raja ) ) do alkaa n : = 4 * sqr ( x ) + sqr ( y ) ; jos ( n <= raja ) ja ( ( n mod 12 = 1 ) tai ( n mod 12 = 5 )) niin on_alkuluku [ n ] := ei ole alkuluku [ n ] ; n := n - sqr ( x ) ; jos ( n <= raja ) ja ( n mod 12 = 7 ) niin on_alkuluku [ n ] := ei ole alkuluku [ n ] ; n := n - 2 * sqr ( y ) ; jos ( x > y ) ja ( n < = raja ) ja ( n mod 12 = 11 ) niin on_alkuluku [ n ] : = ei ole alkuluku [ n ] ; loppu ; jos i := 5 katkaistaan ( sqrt ( raja )) , aloita jos on_alkuluku [ i ] sitten aloita k : = sqr ( i ) ; n := k ; kun taas n <= raja do alkaa on_alkuluku [ n ] := false ; n := n + k ; loppu ; loppu ; loppu ; on_alkuluku [ 2 ] := tosi ; on_alkuluku [ 3 ] := tosi ; loppu ; aloita annostelu ( 10000 ) ; for jj := 1 - 10000 do if is_prime [ jj ] then writeln ( jj ) ; loppua .

Katso myös

Linkit

↑ A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms Arkistoitu 3. helmikuuta 2007, 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. Pyöräseulan selittäminen // Acta Informatica. - 1982. - Voi. 17 . - s. 477-485 .
↑ 1 2 D. J. Bernstein. Primegen (1997). Käyttöpäivä: 26. syyskuuta 2010. Arkistoitu alkuperäisestä 27. huhtikuuta 2011. (määrätön)
↑ Paul Pritchard. Parannetut inkrementaaliset alkulukuseulat . - Springer-Verlag, 1994. - P. 280-288 .
↑ Brain Dunten, Julie Jones, Jonathan Sorenson. Tilatehokas nopea alkulukuseula // Tiedonkäsittelykirjeet. - 1996. - Ei. 59 . - s. 79-84 .