Atkin szitája

Az Atkin-szita egy algoritmus az összes prímszám megtalálására egy adott N egész számig. Az algoritmust A. O. L. Atkin készítetteés D. Yu. Bernstein[1] [2] . A szerzők által deklarált algoritmus aszimptotikus sebessége megfelel a korábban ismert legjobb szitáló algoritmusok sebességének, de azokhoz képest az Atkin-szita kevesebb memóriát igényel.

Leírás

Az algoritmus fő ötlete az irreducibilis másodfokú formák használata (a számok ax 2 + 2 -vel való ábrázolása ). A korábbi algoritmusok alapvetően az Eratoszthenész szitájának különféle módosításai voltak, amelyek a számok redukált alakok (általában xy szorzat formájában ) történő ábrázolását alkalmazták.

Egyszerűsített formában az algoritmus a következőképpen ábrázolható:

Minden szám, amely ( modulo 60) 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, A 42, 44, 46, 48, 50, 52, 54, 56 vagy 58 osztható 2-vel, ezért biztosan nem prímszámok. Minden szám, amely egyenlő (modulo 60) 3, 9, 15, 21, 27, 33, 39, 45, 51 vagy 57-tel, osztható 3-mal, és szintén nem prímszám. Az 5-tel, 25-tel, 35-tel vagy 55-tel egyenlő (modulo 60) minden szám osztható 5-tel, és szintén nem prímszám. Mindezek a maradékok (modulo 60) figyelmen kívül maradnak.
- Minden szám, amely (modulo 60) 1, 13, 17, 29, 37, 41, 49 vagy 53, 4-gyel osztva 1 marad. Ezek a számok akkor és csak akkor prímek, ha az egyenlet megoldásainak száma 4 x 2 + y 2 = n páratlan, és maga a szám nem többszöröse egyetlen prímnégyzetnek sem ( en:négyzet nélküli egész szám ).
- A (60. modul) 7, 19, 31 vagy 43 számok maradéka 1, ha elosztjuk 6-tal. Ezek a számok akkor és csak akkor prímszámúak, ha a 3 x 2 + y 2 = n egyenlet megoldásainak száma páratlan és maga a szám nem többszöröse egy prím négyzetének.
- A (60. modul) 11, 23, 47 vagy 59 számok maradéka 11, ha elosztjuk 12-vel. Ezek a számok akkor és csak akkor prímszámúak, ha az egyenlet megoldásainak száma 3 x 2 − y 2 = n ( ahogy x > y ) páratlan, és maga az n szám nem többszöröse egy prím négyzetének.
- Az algoritmus egy külön lépése áthúzza azokat a számokat, amelyek a prímszámok négyzeteinek többszörösei. Mivel a szóban forgó számok egyike sem osztható 2-vel, 3-mal vagy 5-tel, ezért ennek megfelelően a négyzeteikkel sem oszthatók. Ezért annak ellenőrzése, hogy egy szám nem többszöröse egy prím négyzetének, nem tartalmazza a 2 2 , 3 2 és 5 2 értékeket .

Szegmentálás

A memóriaigény csökkentése érdekében a "szitálás" részenként (szegmensek, blokkok) történik, amelyek mérete kb . ${\sqrt N}$

Elővetítés

A dolgok felgyorsítása érdekében az algoritmus figyelmen kívül hagy minden olyan számot, amely az első néhány prímszám (2, 3, 5, 7, ...) valamelyikének többszöröse. Ez a Paul Pritchard által korábban javasolt szabványos adatstruktúrák és adatfeldolgozó algoritmusok használatával történik [3 ] . Angol néven ismertek . kerekes szitálás . Az első prímek számát az adott N számtól függően választjuk ki . Elméletileg azt javasolják, hogy az első prímszámokat körülbelül -ig vegyük . Ez lehetővé teszi számunkra, hogy egy tényezővel javítsuk az algoritmus sebességének aszimptotikus becslését . Ebben az esetben további memória szükséges, amely az N növekedésével korlátos . A memóriaigény növekedését a becslések szerint . ${\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 )))$

Az egyik szerző honlapján [4] bemutatott verzió egymilliárdig ( ) minden prímszám keresésére van optimalizálva , és a 2, 3, 5 és 7 többszörösei ki vannak zárva a számításokból (2 × 3 × 5 × 7 = 210). ${\sqrt {\log 10^{9}}}\approx {\sqrt {\log 2^{30}}}={\sqrt {30}}\kb. 5{,}5$

Nehézségi fok

A [2] szerzői szerint az algoritmus aszimptotikus bonyolultságú , és memóriabiteket igényel . Korábban ismertek olyan algoritmusokat, amelyek ugyanolyan aszimptotikusan gyorsak voltak, de lényegesen több memóriát igényelnek [5] [6] . Elméletileg ez az algoritmus a maximális sebességet a legalacsonyabb memóriaigénnyel kombinálja. Az algoritmus megvalósítása, amelyet az egyik szerző végez, meglehetősen nagy gyakorlati sebességet mutat [4] . ${\displaystyle \mathop {O} {\big (}N/(\log \log N){\big )))$ ${\displaystyle \mathop {O} {\Big (}N^{{\frac {1}{2}}+\mathop {o} (1)}{\Big )))$

Az algoritmus kétféle optimalizálást alkalmaz, ami jelentősen növeli a hatékonyságát (az egyszerűsített változathoz képest).

Az alábbiakban bemutatjuk a C programozási nyelv egyszerűsített verziójának megvalósítását, amely bemutatja az algoritmus fő gondolatát - a másodfokú formák használatát:

int limit = 1000 ; int sqr_lim ; bool is_prím [ 1001 ]; int x2 , y2 ; int i , j ; int n ; // Szita inicializálása sqr_lim = ( int ) sqrt (( long double ) limit ); for ( i = 0 ; i <= határ ; ++ i ) is_prím [ i ] = hamis ; is_prím [ 2 ] = igaz ; is_prím [ 3 ] = igaz ; // Feltehetően prímek olyan egész számok, amelyek páratlan // reprezentációi vannak az adott négyzet alakzatokban. // x2 és y2 i és j négyzetek (optimalizálás). 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 <= határérték ) && ( n % 12 == 1 || n % 12 == 5 )) is_prím [ n ] = ! is_prím [ n ]; // n = 3 * x2 + y2; n = x2 ; // Optimalizálás if (( n <= limit ) && ( n % 12 == 7 )) is_prím [ n ] = ! is_prím [ n ]; // n = 3 * x2 - y2; n = 2 * y2 ; // Optimalizálás if (( i > j ) && ( n <= limit ) && ( n % 12 == 11 )) is_prím [ n ] = ! is_prím [ n ]; } } // A prímszámok négyzeteinek többszöröseinek kiszűrése az [5, sqrt(limit)] intervallumban. // (a főszínpad nem tudja kiszűrni őket) for ( i = 5 ; i <= sqr_lim ; ++ i ) { if ( is_prím [ i ]) { n = i * i ; for ( j = n ; j < = határ ; j + = n ) is_prím [ j ] = hamis ; } } // Prímszámok listájának nyomtatása a konzolra. printf ( "2, 3, 5" ); for ( i = 6 ; i <= limit ; ++ i ) { // a 3-mal és 5-tel való oszthatóság ellenőrzése hozzáadásra került. Az algoritmus eredeti verziójában nincs rá szükség. if (( is_prím [ i ]) && ( i % 3 != 0 ) && ( i % 5 != 0 )) printf ( ", %d" , i ); }

Az algoritmus Pascal verziója

programatkin ; _ var is_prime : logikai tömb [ 1 .. 10001 ] ; _ jj : int64 ; eljárás dosieve ( határérték : int64 ) ; var i , k , x , y : int64 ; n : int64 ; start 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 ) ; ha ( n <= limit ) és ( ( n mod 12 = 1 ) vagy ( n mod 12 = 5 )) akkor_prím [ n ] := nem prím [ n ] ; n := n - sqr ( x ) ; ha ( n <= limit ) és ( n mod 12 = 7 ) akkor_prím [ n ] : = nem prím [ n ] ; n := n - 2 * sqr ( y ) ; ha ( x > y ) és ( n <= limit ) és ( n mod 12 = 11 ) akkor_prím [ n ] : = nem prím [ n ] ; vége ; 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 ; vége ; vége ; vége ; is_prím [ 2 ] := igaz ; is_prím [ 3 ] := igaz ; vége ; dosieve kezdete ( 10000 ) ; for jj := 1 - 10000 do if is_prime [ jj ] then writeln ( jj ) ; vége .

Lásd még

Linkek

↑ A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms Archivált : 2007. február 3., a Wayback Machine ( 1999).
↑ 1 2 A. O. L. Atkin, D. J. Bernstein, Prime sieves using binary quadratic forms , Math. Összeg. 73 (2004), 1023-1030.
↑ Pritchard, Paul. A kerékszita magyarázata // Acta Informatica. - 1982. - 1. évf. 17 . - P. 477-485 .
↑ 1 2 D. J. Bernstein. Primegen (1997). Hozzáférés dátuma: 2010. szeptember 26. Az eredetiből archiválva : 2011. április 27. (határozatlan)
↑ Paul Pritchard. Továbbfejlesztett növekményes prímszámú sziták . - Springer-Verlag, 1994. - P. 280-288 .
↑ Brain Dunten, Julie Jones, Jonathan Sorenson. Helytakarékos gyors prímszám-szita // Információfeldolgozási levelek. - 1996. - Nem. 59 . - 79-84 . o .