Sil av Eratosthenes

Eratosthenes såll är en algoritm för att hitta alla primtal upp till något heltal n , som tillskrivs den antika grekiske matematikern Eratosthenes av Kirensky [1] . Som i många fall talar namnet på algoritmen här om principen för dess funktion, det vill säga silen innebär filtrering , i det här fallet, filtrering av alla tal utom primtal. När du går igenom listan finns de nödvändiga siffrorna kvar, och de onödiga (de kallas sammansatta ) exkluderas.

Historik

Denna metod beskrivs i "Introduktion till aritmetik" av Nicomachus av Geras . Nicomachus namnger Eratosthenes som författare till metoden . Iamblichus gör samma sak i sin kommentar till detta verk av Nicomachus.

Namnet "sil" gavs till metoden eftersom de på Eratosthenes tid skrev siffror på en tablett täckt med vax och genomborrade hål på de platser där sammansatta siffror skrevs . Därför var tabletten ett slags såll genom vilken alla sammansatta tal ”siktades”, och endast primtal återstod [2] .

Algoritm

För att hitta alla primtal som inte är större än ett givet tal n , enligt Eratosthenes metod, måste du utföra följande steg:

Skriv ut i rad alla heltal från två till n (2, 3, 4, ..., n ).
Låt variabeln p initialt vara lika med två, det första primtalet.
Stryk över siffrorna från 2 p till n i listan, räknat i steg av p (dessa kommer att vara multiplar av p : 2 p , 3 p , 4 p , …).
Hitta det första okorsade talet i listan som är större än p , och tilldela värdet p till det numret.
Upprepa steg 3 och 4 så länge som möjligt.

Nu är alla okrossade tal i listan alla primtal från 2 till n .

I praktiken kan algoritmen förbättras enligt följande. I steg #3 kan siffror strykas över, med början omedelbart med p 2 , eftersom alla mindre multiplar av p nödvändigtvis har en primtalsdelare mindre än p, och de är redan överstrukna vid det här laget. Och följaktligen kan algoritmen stoppas när p2 blir större än n . [3] Dessutom är alla primtal utom 2 udda, och därför kan de betraktas som steg om 2 p , med början på p 2 .

Exempel för n = 30

Låt oss skriva naturliga tal, från 2 till 30 i rad:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Den första siffran i listan, 2 är primtal. Låt oss gå igenom en serie siffror och stryka över alla tal som är multiplar av 2 (det vill säga varje sekund, som börjar med 2 2 = 4 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Nästa okorsade tal, 3 , är primtal. Låt oss gå igenom en serie siffror och stryka över alla tal som är multiplar av 3 (det vill säga var tredje, som börjar med 3 2 = 9 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Nästa okorsade tal, 5 , är primtal. Låt oss gå igenom en serie siffror och stryka över alla multiplar av 5 (det vill säga var femte, börjar med 5 2 = 25 ):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Nästa okryssade nummer är 7 . Dess kvadrat, 49 , är större än 30 , så det är allt. Alla sammansatta siffror är redan överstrukna:

2 3 5 7 11 13 17 19 23 29

Pseudokod

Optimerad implementering (som börjar med rutor) i pseudokod [4] [5] :

Inmatning : naturligt tal n Utdata : alla primtal från 2 till n . Låt A vara en boolesk matris indexerad med siffror från 2 till n , ursprungligen fylld med sanna värden . för i := 2, 3, 4, ... medan i 2 ≤ n : om A [ i ] = sant : för j := i 2 , i 2 + i , i 2 + 2 i , ..., medan j ≤ n : tilldela A [ j ] := falskt return : alla tal i där A [ i ] = sant .

Algoritmens komplexitet

Algoritmens komplexitet motsvarar operationer för att kompilera en tabell med primtal upp till [6] . $O(n\log(\log n))$ $n$

Bevis på komplexitet

När valt , för varje primtal , kommer en inre loop [7] att exekveras , som kommer att utföra åtgärder. Algoritmens komplexitet kan erhållas från uppskattningen av följande värde: $n\in \mathbb {N}$ $p\in {\mathbb {P}}\colon p\leq n$ ${\frac {n}{p))$

$\sum \limits _{{p\in {\mathbb {P}}\colon p\leq n}}{{\frac {n}{p}}}=n\cdot \sum \limits _{{p\ i {\mathbb {P}}\colon p\leq n}}{{\frac {1}{p}}}$

Eftersom antalet primtal mindre än eller lika med utvärderas som , och som en konsekvens är det primtal ungefär lika med , då kan summan konverteras: $n$ ${\frac {n}{\ln n))$ $k$ $k\ln k$

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}\approx {\frac {1}{2}}+\summa \ gränser _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}$

Här separeras summan för det första primtalet från summan för att undvika division med noll. Denna summa kan uppskattas av integralen

${\frac {1}{2}}+\sum _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\approx \int \limits _{2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\,dk=\ln \ln k{\Bigr |}_{ 2}^{\frac {n}{\ln n}}=\ln \ln {\frac {n}{\ln n}}-\ln \ln 2=\ln(\ln n-\ln \ln n)-\ln \ln 2\ca \ln \ln n$

Resultatet är för det ursprungliga beloppet:

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {n}{p))\approx n\ln \ln n+o(n)$

Ett mer rigoröst bevis (och ger en skarpare uppskattning upp till konstanta faktorer) kan hittas i Hardy och Wrights "An Introduction to the Theory of Numbers" [8] .

Metodändringar

Obegränsad, gradvis variation

I denna variant beräknas primtalen sekventiellt, utan övre gräns, [9] som talen mellan de sammansatta talen, som beräknas för varje primtal p , med början från dess kvadrat, med steget p (eller för udda primtal 2p ) [3] . Kan representeras symboliskt i dataflödesparadigmet som

primtal = [ 2 ..] \ [[ p² , p² + p ..] för p i primtal ]

använder listabstraktionsnotation , där \anger skillnaden mellan aritmetiska progressioner .

Det första primtal 2 (bland ökande positiva heltal ) är känt i förväg, så det finns ingen ond cirkel i denna självrefererande definition .

Pseudokod för stegvis sållning, i en ineffektiv implementering för enkelhetens skull (jämför med följande alternativ):

primtal = sil [ 2.. ] där sil [ p , ... xs ] = [ p , ... sil ( xs \ [ p² , p² + p ..])]

Räkna upp divisorer

Sållen av Eratosthenes förväxlas ofta med algoritmer som filtrerar bort sammansatta tal steg för steg , och testar vart och ett av kandidattalen för delbarhet med ett primtal i varje steg. [tio]

Den välkända funktionskoden av David Turner 1975 [11] förväxlas ofta med Eratosthenes sikt, [10] men i själva verket [9] är detta en suboptimal variant med uppräkning av divisorer (i den optimala varianten, divisorer större än kvadratroten av talet som testas används inte). I pseudokod,

primtal = sikt [ 2.. ] där sikt [ p , ... xs ] = [ p , ... sikt [ x i xs om x%p > 0 ]]

Segmenterad sikt

Som Sorenson noterar är huvudproblemet med implementeringen av sikten av Eratosthenes på datorer inte antalet utförda operationer, utan kraven på mängden minne som är upptaget (hans anmärkning hänvisar dock till den nu föråldrade DEC VAXstation 3200-datorn, släppt år 1989). [5] För stora värden på n kan intervallet för primtal överskrida tillgängligt minne; värre, även för relativt små n , är användningen av minnescachen långt ifrån optimal, eftersom algoritmen, som passerar genom hela arrayen, bryter mot principen om lokalisering av referenser .

För att lösa det presenterade problemet används en segmenterad sikt, där endast en del av primtalsintervallet siktas per iteration. [12] Denna metod har varit känd sedan 1970-talet och fungerar enligt följande: [5] [13]

Vi delar upp området från 2 till n i segment (segment) av någon längd Δ ≤ √ n .
Vi hittar alla primtal i det första segmentet med hjälp av en vanlig sil.
Vart och ett av de efterföljande segmenten slutar på något nummer m . Vi hittar alla primtal i segmentet enligt följande:
1. Skapa en boolesk matris med storleken
Δ
För varje primtal p ≤ √ m från de som redan hittats, markerar vi i arrayen som "icke-primtal" alla tal som är multiplar av p , sorterar genom talen med steget p , med början från den minsta multipeln av p - tal i detta segment.

Om talet Δ väljs till √ n , så uppskattas minneskomplexiteten för algoritmen vara O ( √ n ) , och operationskomplexiteten förblir densamma som den för den konventionella sikten av Eratosthenes. [13]

För fall där n är så stort att alla siktade primtal mindre än √ n inte kan passa i minnet, vilket krävs av den segmenterade siktalgoritmen, långsammare, men med mycket lägre minneskrav, används algoritmer, såsom Sorenson-sikten . [fjorton]

Eulers såll

Beviset på Eulers identitet för Riemann zeta-funktionen innehåller en mekanism för att filtrera bort sammansatta tal som liknar Eratosthenes såll, men på ett sådant sätt att varje sammansatt nummer tas bort från listan endast en gång. En liknande sikt beskrivs i Gries & Misra 1978 som en linjär tidssikt (se nedan ).

Den initiala listan sammanställs med början från siffran 2 . I varje steg av algoritmen tas det första talet i listan som nästa primtal, vars resultat av produkten av varje nummer i listan markeras för efterföljande borttagning. Därefter tas det första numret och alla markerade nummer bort från listan, och processen upprepas igen:

[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 7 7 9 61 63 6 9 7 7 7 [3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 ... [4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ... [5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ... [...]

Här är ett exempel som börjar med udda tal, efter det första steget i algoritmen. Sålunda, efter det k -te steget, innehåller arbetslistan endast samprimtal med de första k primtalen (d.v.s. tal som inte är multiplar av någon av de första k primtalen), och börjar med (k+1) - :te primtalen. Alla tal i listan mindre än kvadraten på dess första tal är primtal.

I pseudokod,

primtal = sikt [ 2.. ] där sikt [ p , ... xs ] = [ p , ... sikt ( xs \ [ p² , ... p * xs ])]

Sila endast för udda nummer

Eftersom alla jämna tal , förutom 2, är sammansatta, är det möjligt att inte bearbeta jämna tal alls, utan att endast arbeta med udda tal. Först kommer det att halvera mängden minne som krävs. För det andra kommer det att minska antalet operationer som utförs av algoritmen (med ungefär hälften).

I pseudokod:

primtal = [2, ...sil [ 3,5.. ]] där sil [ p , ... xs ] = [ p , ...sil ( xs \ [ p² , p² + 2p ..])]

Detta kan generaliseras till samprimtal inte bara med 2 (d.v.s. udda tal), utan också med 3, 5, etc. .

Minska mängden minne som förbrukas

Eratosthenes algoritm fungerar faktiskt på minnesbitar . Därför kan du avsevärt spara minnesförbrukning genom att lagra variabler av boolesk typ inte som byte utan som bitar, det vill säga byte av minne. $n$ $n$ $n$ $n$ $n/8$

Detta tillvägagångssätt - "bitkomprimering" - komplicerar driften av dessa bitar. Varje läsning eller skrivning av en bit kommer att representera flera aritmetiska operationer. Men å andra sidan är kompaktheten i minnet avsevärt förbättrad. Stora intervall får plats i cacheminnet, som fungerar mycket snabbare än vanligt, så när man arbetar i segment ökar den totala hastigheten.

Sikt av Eratosthenes med linjär körtid

Denna algoritm hittar för varje tal i i intervallet [2...n] dess minsta primtalsdivisor lp[i] ( lp står för minsta primtal ) .

Det stöds också en lista över alla primtal, arrayen pr[] , initialt tom. Under algoritmens gång kommer denna array att fyllas gradvis.

Inledningsvis kommer alla lp[i] -värden att fyllas med nollor.

Iterera sedan över det aktuella talet i från 2 till n . Det kan finnas två fall här:

lp[i] = 0 : detta betyder att i är primtal, eftersom inga andra divisorer har hittats för det.

Därför måste vi tilldela lp[i] = i och lägga till i i slutet av listan pr[] .

lp[i] ≠ 0 : detta betyder att det nuvarande talet i är sammansatt och dess lägsta primtalsdelare är lp[i] .

I båda fallen börjar sedan processen att ordna värden i lp[i] -matrisen : du bör ta tal som är multiplar av i och uppdatera deras lp[]- värde . Men huvudmålet är att lära sig hur man gör det på ett sådant sätt att varje nummer i slutändan har värdet lp[] högst en gång.

Det hävdas att detta kan göras på detta sätt. Tal av formen x = p ⋅ i anses vara , där p successivt är lika med alla primtal som inte överstiger lp[i] (bara för detta var det nödvändigt att lagra en lista över alla primtal).

För alla siffror av det här slaget sätter vi ett nytt värde lp[x] - det ska vara lika med p [15] .

Pseudokod Inmatning : naturligt tal n Låt pr vara en heltalsmatris, initialt tom; lp - heltalsmatris, indexerad från 2 till n , utfylld med nollor för i := 2, 3, 4, ..., upp till n : om lp [ i ] = 0 : lp [ i ] := i pr [] += { i } för p av pr medan p ≤ lp [ i ] och p*i ≤ n : lp [ p*i ] := p Utdata : alla nummer i array pr .

Algoritmens komplexitet i praktiken

The Sieve of Eratosthenes är ett populärt sätt att utvärdera datorns prestanda. [16] Som framgår av ovanstående bevis på algoritmens komplexitet, efter att ha blivit av med konstanten och termen mycket nära noll (ln (ln n - ln ln n ) - ln ln 2 ≈ ln ln n ) , tidskomplexiteten för att beräkna alla primtal mindre än n approximeras av följande relation O ( n ln ln n ) . Algoritmen har emellertid exponentiell tidskomplexitet med avseende på storleken på inmatningen, vilket gör den till en pseudopolynomisk algoritm . Minnet som krävs för den underliggande algoritmen är O ( n ) . [17]

Den segmenterade versionen har samma operativa komplexitet O ( n ln ln n ) , [8] . som den icke-segmenterade versionen, men minskar minnesfotavtrycket som krävs till en segmentstorlek (storleken på ett segment är mycket mindre än storleken på hela serien av primtal), vilket är O (√ n /ln n ) . [18] Det finns också en optimerad segmenterad sikt av Eratosthenes, vilket är mycket sällsynt i praktiken. Den är inbyggd i O ( n ) operationer och tar O ( √n ln ln n /ln n ) bitar av minne. [17] [19] [18]

I praktiken visar det sig att uppskattningen av ln ln n inte är särskilt exakt även för de maximala praktiska intervallen som 10 16 . [19] Efter att ha blivit bekant med ovanstående bevis på komplexitet är det inte svårt att förstå varifrån felaktigheten i uppskattningen kom. Avvikelsen med uppskattningen kan förklaras på följande sätt: inom detta praktiska siktningsintervall har konstanta förskjutningar en betydande effekt. [8] Den mycket långsamt växande termen ln ln n blir alltså inte tillräckligt stor för att konstanterna ska kunna försummas ganska bra förrän n närmar sig oändligheten, vilket naturligtvis ligger utanför gränserna i alla tillämpade siktningsintervall. [8] Detta faktum visar att för nuvarande indata är prestandan för sikten av Eratosthenes mycket bättre än man skulle förvänta sig med endast asymptotiska tidskomplexitetsuppskattningar. [19]

Sållen av Eratosthenes är snabbare än den ofta jämförda Atkin-sikten endast för värden på n mindre än 10 10 . [20] Detta är sant om man antar att operationerna tar ungefär samma tid i CPU- cykler , vilket är ett rimligt antagande för en enda algoritm som arbetar på en enorm bitmapp. [21] Givet detta antagande verkar det som att Atkin-sikten är snabbare än den maximala faktoriserade sikten av Eratosthenes för n över 10 13 , men sådana siktningsområden skulle kräva en enorm mängd RAM-utrymme även om "bitpackning" användes. [21] Avsnittet om den segmenterade versionen av sikten av Eratosthenes visar dock att antagandet om att upprätthålla jämlikhet i den tid som spenderas på en operation mellan de två algoritmerna inte uppfylls av segmentering. [13] [20] Detta gör i sin tur att Atkin-silen (icke-segmenterad) fungerar långsammare än den segmenterade sikten från Eratosthenes med ökande siktningsintervall, till priset av en minskad tid per operation för den andra.

Att använda den stora O -notationen är inte heller det rätta sättet att jämföra praktiska prestanda även för variationer av sikten av Eratosthenes, eftersom denna notation ignorerar konstanter och förskjutningar, vilket kan vara mycket betydelsefullt för tillämpningsområdena. [8] Till exempel, en variant av sikten av Eratosthenes känd som Pritchard sieve [17] har O ( n ) prestanda , [19] men dess grundläggande implementering kräver antingen "one big array"-algoritmen [18] (dvs. använder en vanlig array, där alla nummer lagras upp till n ), vilket begränsar dess användningsområde till mängden tillgängligt minne, eller så måste den segmenteras för att minska minnesanvändningen. Pritchards arbete har reducerat minneskraven till det yttersta, men kostnaden för denna minnesförbättring är beräkningskomplexitet, vilket ökar den operativa komplexiteten hos algoritmerna. [19]

Ett populärt sätt att påskynda algoritmer som fungerar med stora arrayer av tal är all slags faktorisering . [22] Användningen av faktoriseringsmetoder ger en betydande minskning av operationell komplexitet på grund av optimeringen av indatamatrisen. [23] [22] Ringfaktorisering används ofta för indexalgoritmer. [23] [24] Algoritmerna som övervägs i denna artikel för att hitta alla primtal upp till ett givet n , liknande sikten från Eratosthenes, är indexbaserade, vilket gör det möjligt att tillämpa ringfaktoriseringsmetoden på dem. [25]

Trots den teoretiska accelerationen som erhålls med ringfaktorisering finns det i praktiken faktorer som inte beaktas i beräkningarna, men som kan ha en betydande inverkan på algoritmens beteende, vilket som ett resultat kanske inte ger den förväntade ökningen av prestanda. [26] Betrakta de viktigaste av dem:

Multiplikation och division. I analytiska beräkningar antas det att hastigheten för att utföra aritmetiska operationer är likvärdig. Men i själva verket är det inte så, och multiplikation och division är mycket långsammare än addition och subtraktion. Således påverkar denna faktor inte sikten av Eratosthenes på något sätt, eftersom den bara använder addition och subtraktion, men är ganska signifikant för Pitchard-sikten (ett av resultaten av komplikationen av beräkningarna som nämns ovan). [27]
Kompilatoroptimering. Kompilatorn optimerar alla program i kompileringsstadiet för mer korrekt exekvering av maskinen. Men det är ofta väldigt svårt att säga vilket bidrag en given optimering ger, och om detta bidrag kommer att vara detsamma för två olika algoritmer. [28]
cache . Processorn använder en cache för att påskynda hämtningen av instruktioner och data från minnet. Att ha en cache gör att program som använder lokaliserade länkar körs snabbare. Men sållningsalgoritmer för primtal som använder hög faktorisering genererar ofta slumpmässiga minnesreferenser, vilket minskar deras prestanda. [28]

För att illustrera faktoriseringens bidrag till prestanda för sållningsalgoritmer ges två tabeller nedan. Tabellerna visar resultaten av att mäta den verkliga exekveringstiden för Eratosthenes sikt och Pitchards sikt i sekunder för olika intervall av n och olika grader av ringfaktorisering. E i och P i är beteckningarna för sikten av Eratosthenes respektive Pitchard, där index i anger graden av ringfaktorisering. E 0 och P 0 betyder ingen faktorisering. [28]

n	E0 _	E 1	E 2	E 3	E 4	E 5
500	0,00043	0,00029	0,00027	0,00048	0,00140	0,01035
5 000	0,00473	0,00305	0,00254	0,00293	0,00551	0,03207
50 000	0,05156	0,03281	0,02617	0,02578	0,03164	0,10663
500 000	0,55817	0,35037	0,28240	0,28358	0,28397	0,47028
5000000	6,06719	3,82905	3,20722	3,25214	3,28104	3,38455

Det kan ses av tabellen att sikten av Eratosthenes med en genomsnittlig faktoriseringsgrad E 2 har bäst prestanda . Detta faktum kan förklaras av inverkan av cachefaktorn som diskuterats ovan på algoritmer med en hög grad av faktorisering.

n	P0 _	P1 _	P2 _	P3 _	P4 _	P5 _
500	0,00147	0,00074	0,00050	0,00051	0,00095	0,00649
5 000	0,01519	0,00777	0,00527	0,00453	0,00430	0,00973
50 000	0,15507	0,08203	0,05664	0,04843	0,04180	0,04413
500 000	1,60732	0,86254	0,61597	0,53825	0,47146	0,43787
5000000	16,47706	9,00177	6,57146	5,83518	5,27427	4,88251

När n ökar , blir förhållandet mellan gånger mer och mer till förmån för Eratosthenes såll, och på intervallet n = 5000000 är det konsekvent snabbare för alla faktoriseringar. Detta faktum bekräftar återigen hastighetsförlusten för Pitchard-sikten på grund av komplexa beräkningar. [19]

Se även

Anteckningar

↑ Nicomachus of Geras , Introduction to Arithmetic , I, 13. [1]
↑ Depman I. Ya. Aritmetikens historia. En guide för lärare. - M . : Education , 1965. - S. 133. - 34 000 ex.
↑ 12 Horsley , Rev. Samuel, FRS, " Κόσκινον Ερατοσθένους eller, The Sieve of Eratosthenes. Att vara en redogörelse för hans metod för att hitta alla primtal," Philosophical Transactions (1683-1775), Vol. 62. (1772), sid. 327-347 Arkiverad 2 oktober 2018 på Wayback Machine .
↑ Sedgewick, Robert. Algoritmer i C++ (neopr.) . - Addison-Wesley , 1992. - ISBN 0-201-51059-6 . , sid. 16.
↑ 1 2 3 Jonathan Sorenson, An Introduction to Prime Number Sieves , Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, 2 januari 1990 (användningen av optimering av att börja från kvadrater, och alltså endast använda talen vars kvadrat ligger under den övre gränsen, visas).
↑ Pritchard, Paul, "Linjära primtalssiktar: ett släktträd," Sci. Comput. Programmering 9 :1 (1987), sid. 17-35.
↑ Strängt taget utförs den inre slingan för varje primtal , men = , så traditionellt, för korthetens skull, utelämnas kvadratroten. $p\in \mathbb {P} \colon p\leq ({\sqrt {n)))$ $O(\log(\log n))$ $O(\log(\log({\sqrt {n}})))$
↑ 1 2 3 4 5 Hardy och Wright "An Introduction to the Theory of Numbers, s. 349
↑ 1 2 O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes" Arkiverad 9 november 2017 på Wayback Machine , Journal of Functional Programming, publicerad online av Cambridge University Press 9 oktober 2008 doi : 10.1017/S0956790680407 .
↑ 1 2 Colin Runciman, "FUNKTIONELL PÄRL: Lata hjulsilar och spiraler av primtal" , Journal of Functional Programming, Volym 7, nummer 2, mars 1997; även här Arkiverad 19 oktober 2012 på Wayback Machine .
↑ Turner, David A. SASL språkhandbok. Tech. rept. CS/75/1. Institutionen för beräkningsvetenskap, University of St. Andrews 1975. ( primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0)
↑ Crandall & Pomerance, Prime Numbers: A Computational Perspective , andra upplagan, Springer: 2005, s. 121-24.
↑ 1 2 3 Bays, Carter; Hudson, Richard H. Den segmenterade sikten av Eratosthenes och primtal i aritmetiska progressioner till 10 12 // BIT : journal. - 1977. - Vol. 17 , nr. 2 . - S. 121-127 . - doi : 10.1007/BF01932283 .
↑ J. Sorenson, The pseudosquares prime sieve Arkiverad 17 oktober 2012 på Wayback Machine , Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).
↑ David Gries, Jayadev Misra. En linjär sållalgoritm för att hitta primtal [1978]
↑ Peng, T.A. One Million Primes Through the Sieve , BYTE (hösten 1985), s. 243–244. Hämtad 19 mars 2016.
↑ 1 2 3 Paul Pritchard, En sublinjär additiv sikt för att hitta primtal, Communications of the ACM 24 (1981), 18-23. MR : 600730
↑ 1 2 3 Paul Pritchard, Fast compact prime number sieves (bland andra), Journal of Algorithms 4 (1983), 332-344. MR : 729229
↑ 1 2 3 4 5 6 Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477-485. MR : 685983
↑ 1 2 A. OL ATKIN OCH DJ BERNSTEIN. PRIMA SIEVER ANVÄNDER BINÄRA KVADRATISKA FORMER // BEräkningsmatematik. Arkiverad från originalet den 24 december 2017.
↑ 1 2 Meertens, Lambert. Beräkning av Eratosthenes sikt // Journal of functional programmering.
↑ 1 2 V.A. Minaev, N.P. Vasiliev, V.V. Lukyanov, S.A. Nikonov, D.V. Nikerov. [ http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf INDEXALGORITMER FÖR BERÄKNING AV PRIMTAL MED RINGFAKTORISERINGSMETOD] // VESTNIK. - 2013. - Nr 4 . - S. 29 . Arkiverad från originalet den 22 december 2017.
↑ 1 2 Jonathan Sörenson. En analys av två primtalssiktar // Computer Science Department University of Wisconsin-Madison. - S. 8-10 .
↑ V.A. Minaev, N.P. Vasiliev, V.V. Lukyanov, S.A. Nikonov, D.V. Nikerov. [ http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf INDEXALGORITMER FÖR BERÄKNING AV PRIMTAL MED RINGFAKTORISERINGSMETOD] // VESTNIK. - 2013. - Nr 4 . - S. 30-31 . Arkiverad från originalet den 22 december 2017.
↑ V.A. Minaev, N.P. Vasiliev, V.V. Lukyanov, S.A. Nikonov, D.V. Nikerov. [ http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf INDEXALGORITMER FÖR BERÄKNING AV PRIMTAL MED RINGFAKTORISERINGSMETOD] // VESTNIK. - 2013. - Nr 4 . - S. 30-33 . Arkiverad från originalet den 22 december 2017.
↑ Jonathan Sörenson. En analys av två primtalssiktar // Computer Science Department University of Wisconsin-Madison. - S. 16-18 .
↑ Jonathan Sörenson. En analys av två primtalssiktar // Computer Science Department University of Wisconsin-Madison. - S. 16 .
↑ 1 2 3 Jonathan Sörenson. En analys av två primtalssiktar // Computer Science Department University of Wisconsin-Madison. - S. 17 .

Litteratur

Sikt av Eratosthenes // Elokventia - Yaya. - M . : Soviet Encyclopedia, 1957. - S. 141. - ( Great Soviet Encyclopedia : [i 51 volymer] / chefredaktör B. A. Vvedensky ; 1949-1958, v. 49).
Galperin G. "Bara om primtal" // Kvant . - 1987. - Nr 4 . - S. 10-14.38 .
Opublicerat material från L. Euler om talteori / Russian Academy of Sciences , Institute of the History of Natural Science and Technology , St. Petersburg. fil.; Comp. Matvievskaya G.P. [och så vidare.]; Rep. ed. Nevskaya N.I. - St Petersburg. : Nauka , 1997. - ISBN 5-02-024847-9 .
Prof. D.F. Egorov. Element i talteorin . - State Publishing House Moskva, 1923. (otillgänglig länk)
Kordemsky B. A. Matematisk uppfinningsrikedom . - M. : GIFML, 1958. - 576 sid.

Länkar

Ordböcker och uppslagsverk	Stor dansk Brockhaus och Efron Kroatisk Britannica (online) Brockhaus