Eratosthenovo síto

Eratosthenovo síto je algoritmus pro nalezení všech prvočísel až po nějaké celé číslo n , které je připisováno starověkému řeckému matematikovi Eratosthenovi z Kirenského [1] . Jako v mnoha případech i zde název algoritmu hovoří o principu jeho fungování, to znamená, že síto znamená filtrování , v tomto případě filtrování všech čísel kromě prvočísel. Při procházení seznamu potřebná čísla zůstávají a nepotřebná (nazývají se kompozitní ) jsou vyloučena.

Historie

Tato metoda je popsána v „Úvod do aritmetiky“ od Nicomacha z Geras . Nikomachos jmenuje Eratosthena jako autora metody . Iamblichus dělá totéž ve svém komentáři k tomuto Nicomachovu dílu.

Název „síto“ byl dán této metodě, protože v době Eratosthena psali čísla na desku pokrytou voskem a propichovali otvory v místech, kde se psala složená čísla . Proto byla tableta jakýmsi sítem, přes které byla všechna složená čísla „proseta“ a zůstala pouze prvočísla [2] .

Algoritmus

Chcete-li podle Eratosthenovy metody najít všechna prvočísla, která nejsou větší než dané číslo n , musíte provést následující kroky:

Vypište za sebou všechna celá čísla od dvou do n (2, 3, 4, ..., n ).
Nechť je proměnná p zpočátku rovna dvěma, prvnímu prvočíslu.
V seznamu škrtněte čísla od 2 p do n, počítejte v krocích p (budou to násobky p : 2 p , 3 p , 4 p , …).
Najděte první nezaškrtnuté číslo v seznamu, které je větší než p , a přiřaďte tomuto číslu hodnotu p .
Opakujte kroky 3 a 4 tak dlouho, jak je to možné.

Nyní jsou všechna nezaškrtnutá čísla v seznamu všechna prvočísla od 2 do n .

V praxi lze algoritmus vylepšit následovně. V kroku č. 3 mohou být čísla přeškrtnuta, počínaje ihned p 2 , protože všechny menší násobky p mají nutně prvočíselník menší než p a v této době jsou již proškrtány. A v souladu s tím může být algoritmus zastaven, když p2 bude větší než n . [3] Navíc všechna prvočísla kromě 2 jsou lichá, a tak je lze považovat za kroky 2 p , počínaje p 2 .

Příklad pro n = 30

Zapišme přirozená čísla od 2 do 30 za sebou:

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

První číslo v seznamu, 2 , je prvočíslo. Projdeme si řadu čísel a přeškrtneme všechna čísla, která jsou násobky 2 (tedy každou sekundu, počínaje 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

Další nezaškrtnuté číslo, 3 , je prvočíslo. Projdeme si řadu čísel a přeškrtneme všechna čísla, která jsou násobky 3 (tedy každé třetí, počínaje 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

Další nezaškrtnuté číslo, 5 , je prvočíslo. Projdeme si řadu čísel, přeškrtneme všechny násobky 5 (tedy každé páté, počínaje 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

Další nezaškrtnuté číslo je 7 . Jeho čtverec, 49 , je větší než 30 , takže to je vše. Všechna složená čísla jsou již přeškrtnutá:

2 3 5 7 11 13 17 19 23 29

Pseudokód

Optimalizovaná implementace (počínaje čtverci) v pseudokódu [4] [5] :

Vstup : přirozené číslo n Výstup : všechna prvočísla od 2 do n . Nechť A je booleovské pole indexované čísly od 2 do n , zpočátku naplněna skutečnými hodnotami . for i := 2, 3, 4, ... while i 2 ≤ n : if A [ i ] = true : for j := i 2 , i 2 + i , i 2 + 2 i , ..., while j ≤ n : přiřadit A [ j ] := nepravda return : všechna čísla i , pro která A [ i ] = true .

Složitost algoritmu

Složitost algoritmu se rovná operacím při sestavování tabulky prvočísel až [6] . $O(n\log(\log n))$ $n$

Důkaz složitosti

Když vyberete , pro každé prvočíslo se provede vnitřní smyčka [7] , která provede akce. Složitost algoritmu lze získat odhadem následující hodnoty: $n\in \mathbb {N}$ $p\in {\mathbb {P}}\dvojtečka p\leq n$ ${\frac {n}{p))$

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

Protože počet prvočísel menších nebo rovných je vyhodnocen jako , a v důsledku toho je th prvočíslo přibližně rovno , pak lze součet převést: $n$ ${\frac {n}{\ln n))$ $k$ $k\ln k$

$\sum \limits _{p\in \mathbb {P} \colon p\leq n}{\frac {1}{p}}\cca {\frac {1}{2}}+\součet \ limity _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}$

Zde je sčítanec prvního prvočísla oddělen od součtu, aby nedošlo k dělení nulou. Tento součet lze odhadnout pomocí integrálu

${\frac {1}{2}}+\sum _{k=2}^{\frac {n}{\ln n}}{\frac {1}{k\ln k}}\přibl. \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\cca \ln \ln n$

Výsledek je za původní částku:

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

Přesnější důkaz (a dávat ostřejší odhad až do konstantních faktorů) lze nalézt v Hardyho a Wrightově „Úvodu do teorie čísel“ [8] .

Modifikace metod

Neomezená, postupná variace

V této variantě se prvočísla počítají sekvenčně, bez horní hranice, [9] jako čísla mezi složenými čísly, která se počítají pro každé prvočíslo p , počínaje jeho druhou mocninou, s krokem p (nebo pro lichá prvočísla 2p ) [3] . Může být reprezentován symbolicky v paradigmatu toku dat jako

prvočísla = [ 2 ..] \ [[ p² , p² + p ..] pro p v prvočíslech ]

pomocí notace abstrakce seznamu , kde \označuje rozdíl mezi aritmetickými průběhy .

První prvočíslo 2 (mezi rostoucími kladnými celými čísly ) je známo předem, takže v této sebereferenční definici neexistuje žádný začarovaný kruh .

Pseudokód pro postupné prosévání, neefektivní, pro jednoduchost implementace (srovnejte s následujícími možnostmi):

prvočísla = síto [ 2.. ] kde síto [ p , ... xs ] = [ p , ...síto ( xs \ [ p² , p² + p ..])]

Výčet dělitelů

Eratosthenovo síto je často zaměňováno s algoritmy, které filtrují složená čísla krok za krokem a testují každé z kandidátských čísel na dělitelnost pomocí jednoho prvočísla v každém kroku. [deset]

Známý funkční kód Davida Turnera z roku 1975 [11] je často zaměňován za síto Eratosthena, [10] ale ve skutečnosti [9] jde o suboptimální variantu s výčtem dělitelů (v optimální variantě dělitelé větší než druhá odmocnina z testovaného čísla se nepoužívá). V pseudokódu,

prvočísla = síto [ 2.. ] kde síto [ p , ... xs ] = [ p , ...síto [ x v xs , pokud x%p > 0 ]]

Segmentové síto

Jak poznamenává Sorenson, hlavním problémem implementace síta Eratosthenes na počítačích není počet provedených operací, ale požadavky na množství zabrané paměti (jeho poznámka se však týká dnes již zastaralého počítače DEC VAXstation 3200, vydaného v roce 1989). [5] Pro velké hodnoty n může rozsah prvočísel překročit dostupnou paměť; horší je, že i pro relativně malé n není využití mezipaměti zdaleka optimální, protože algoritmus procházející celým polem porušuje princip lokalizace referencí .

K vyřešení předloženého problému se používá segmentové síto, ve kterém se na iteraci prosévá pouze část rozsahu prvočísel. [12] Tato metoda je známá již od 70. let a funguje následovně: [5] [13]

Rozsah od 2 do n rozdělíme na segmenty (segmenty) nějaké délky Δ ≤ √ n .
Všechna prvočísla najdeme v prvním segmentu pomocí běžného síta.
Každý z následujících segmentů končí na nějakém čísle m . Všechna prvočísla v segmentu najdeme takto:
1. Vytvořte booleovské pole o velikosti
Δ
Pro každé prvočíslo p ≤ √ m z již nalezených označíme v poli jako „neprvočíslo“ všechna čísla, která jsou násobky p , čísla seřadíme s krokem p , počínaje nejmenším násobkem p čísla . v tomto segmentu.

Pokud je číslo Δ zvoleno jako √ n , pak se paměťová složitost algoritmu odhaduje na O ( √ n ) a operační složitost zůstává stejná jako u konvenčního Eratosthenova síta. [13]

Pro případy, kdy n je tak velké, že se všechna prosévaná prvočísla menší než √ n nevejdou do paměti, jak to vyžaduje algoritmus segmentovaného síta, jsou pomalejší, ale s mnohem nižšími požadavky na paměť, používají se algoritmy, jako je Sorensonovo síto . [čtrnáct]

Eulerovo síto

Důkaz Eulerovy identity pro Riemannovu zeta funkci obsahuje mechanismus pro odfiltrování složených čísel podobný Eratosthenovu sítu, ale takovým způsobem, že každé složené číslo je ze seznamu odstraněno pouze jednou. Podobné síto je popsáno v Gries & Misra 1978 jako lineární časové síto (viz níže ).

Počáteční seznam je sestaven od čísla 2 . V každé fázi algoritmu je první číslo v seznamu považováno za další prvočíslo, jehož výsledky součinu každým číslem v seznamu jsou označeny pro následné odstranění. Poté se první číslo a všechna označená čísla odstraní ze seznamu a proces se znovu opakuje:

[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 73 7 7 3 7 9 ... [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 ... [...]

Zde je příklad začínající lichými čísly po prvním kroku algoritmu. Po k -tém kroku tedy pracovní seznam obsahuje pouze souběžná prvočísla s prvními k prvočísly (tj. čísla, která nejsou násobky žádného z prvních k prvočísel) a začíná (k+1) -tým prvočíslem. Všechna čísla v seznamu menší než druhá mocnina jeho prvního čísla jsou prvočísla.

V pseudokódu,

prvočísla = síto [ 2.. ] kde síto [ p , ... xs ] = [ p , ... síto ( xs \ [ p² , ... p * xs ])]

Síto pouze pro lichá čísla

Protože všechna sudá čísla kromě 2 jsou složená, je možné sudá čísla vůbec nezpracovávat, ale pracovat pouze s lichými čísly. Za prvé, sníží množství požadované paměti na polovinu. Za druhé, sníží se počet operací prováděných algoritmem (asi na polovinu).

V pseudokódu:

prvočísla = [2, ...síto [ 3,5.. ]] kde síto [ p , ... xs ] = [ p , ...síto ( xs \ [ p² , p² + 2p ..])]

To lze zobecnit na koprimá čísla nejen s 2 (tj. lichými čísly), ale také s 3, 5 atd . .

Snížení množství spotřebované paměti

Eratosthenesův algoritmus ve skutečnosti pracuje s paměťovými bity . Proto můžete výrazně ušetřit spotřebu paměti tím , že proměnné typu boolean nebudete ukládat jako bajty , ale jako bity, tedy bajty paměti. $n$ $n$ $n$ $n$ $n/8$

Tento přístup – „bitová komprese“ – komplikuje provoz těchto bitů. Jakékoli čtení nebo zápis bitu bude představovat více aritmetických operací. Ale na druhou stranu se výrazně zlepšila kompaktnost v paměti. Velké intervaly se vejdou do mezipaměti, která funguje mnohem rychleji než obvykle, takže při práci v segmentech se celková rychlost zvyšuje.

Eratosthenovo síto s lineární dobou chodu

Tento algoritmus najde pro každé číslo i v intervalu [2...n] jeho minimálního dělitele prvočísel lp[i] ( lp znamená nejmenší prvočíslo ) .

Podporován je také seznam všech prvočísel, pole pr[] , zpočátku prázdné. V průběhu algoritmu bude toto pole postupně zaplňováno.

Zpočátku budou všechny hodnoty lp[i] vyplněny nulami.

Dále iterujte aktuální číslo i od 2 do n . Zde mohou nastat dva případy:

lp[i] = 0 : to znamená , že i je prvočíslo, protože pro něj nebyly nalezeny žádné další dělitele.

Proto musíme přiřadit lp[i] = i a přidat i na konec seznamu pr[] .

lp[i] ≠ 0 : to znamená, že aktuální číslo i je složené a jeho minimální prvočíslo je lp[i] .

V obou případech pak začíná proces uspořádání hodnot v poli lp[i] : měli byste vzít čísla, která jsou násobky i , a aktualizovat jejich hodnotu lp[] . Hlavním cílem je ale naučit se to dělat tak, aby nakonec každé číslo mělo maximálně jednou hodnotu lp[] .

Tvrdí se, že to lze udělat tímto způsobem. Jsou uvažována čísla ve tvaru x = p ⋅ i , kde p se postupně rovná všem prvočíslům nepřesahujícím lp[i] (právě k tomu bylo nutné uložit seznam všech prvočísel).

Pro všechna čísla tohoto druhu zapíšeme novou hodnotu lp[x] - měla by se rovnat p [15] .

Pseudokód Vstup : přirozené číslo n Nechť pr je celočíselné pole, zpočátku prázdné; lp - celočíselné pole, indexované od 2 do n , doplněné nulami pro i := 2, 3, 4, ..., až do n : pokud lp [ i ] = 0 : lp [ i ] := i pr [] += { i } pro p z pr , zatímco p ≤ lp [ i ] a p*i ≤ n : lp [ p*i ] := p Výstup : všechna čísla v poli pr .

Složitost algoritmu v praxi

Sieve of Eratosthenes je oblíbený způsob hodnocení výkonu počítače. [16] Jak je vidět z výše uvedeného důkazu složitosti algoritmu, zbavit se konstanty a členu velmi blízkého nule (ln (ln n - ln ln n ) - ln ln 2 ≈ ln ln n ) časová složitost výpočtu všech prvočísel menších než n je aproximována následujícím vztahem O ( n ln ln n ) . Algoritmus má však exponenciální časovou složitost s ohledem na velikost vstupu, což z něj činí pseudopolynomiální algoritmus . Paměť požadovaná pro základní algoritmus je O ( n ) . [17]

Segmentovaná verze má stejnou provozní složitost O ( n ln ln n ) , [8] . jako nesegmentovaná verze, ale snižuje nároky na paměť na velikost segmentu (velikost segmentu je mnohem menší než velikost celého pole prvočísel), což je O (√ n /ln n ) . [18] Existuje také optimalizované segmentové síto Eratosthenes, které je v praxi velmi vzácné. Je zabudován do O ( n ) operací a zabírá 0 ( √n ln ln n /ln n ) bitů paměti. [17] [19] [18]

V praxi se ukazuje, že odhad ln ln n není příliš přesný ani pro maximální praktické rozsahy jako je 10 16 . [19] Po seznámení se s výše uvedeným důkazem složitosti není těžké pochopit, kde se vzala nepřesnost odhadu. Nesoulad s odhadem lze vysvětlit následovně: v tomto praktickém rozsahu prosévání mají významný vliv konstantní posuny. [8] Velmi pomalu rostoucí člen ln ln n se tedy nestane dostatečně velkým na to, aby byly konstanty docela zanedbané, dokud se n neblíží nekonečnu, což je přirozeně mimo meze v jakémkoli aplikovaném rozsahu prosévání. [8] Tato skutečnost ukazuje, že pro současná vstupní data je výkon Eratosthenova síta mnohem lepší, než by se dalo očekávat při použití pouze asymptotických odhadů časové složitosti. [19]

Eratosthenovo síto je rychlejší než často srovnávané Atkinovo síto pouze pro hodnoty n menší než 10 10 . [20] To platí za předpokladu, že operace trvají zhruba stejnou dobu v cyklech CPU , což je rozumný předpoklad pro jeden algoritmus pracující na obrovské bitmapě. [21] Vzhledem k tomuto předpokladu se zdá, že Atkinovo síto je rychlejší než maximální faktorizované síto Eratosthena pro n nad 10 13 , ale takové rozsahy sít by vyžadovaly obrovské množství místa RAM, i kdyby bylo použito „balení bitů“. [21] Část o segmentované verzi Eratosthenova síta však ukazuje, že předpoklad zachování rovnosti času stráveného jednou operací mezi dvěma algoritmy segmentace nesplňuje. [13] [20] To zase způsobí, že Atkinovo (nesegmentované) síto pracuje pomaleji než segmentované síto Eratosthenes se zvětšujícím se rozsahem síta, za cenu zkrácení doby na operaci na sekundu.

Použití velkého O zápisu také není správný způsob, jak porovnávat praktický výkon i pro variace síta Eratosthenes, protože tento zápis ignoruje konstanty a offsety, které mohou být velmi významné pro aplikační rozsahy. [8] Například jedna varianta Eratosthenova síta známá jako Pritchardovo síto [17] má výkon O ( n ) , [19] ale její základní implementace vyžaduje buď algoritmus „jedno velké pole“ [18] (tj. pomocí běžného pole, ve kterém jsou uložena všechna čísla do n ), což omezuje rozsah jeho použití na velikost dostupné paměti, nebo musí být segmentováno, aby se snížilo využití paměti. Pritchardova práce snížila požadavky na paměť na limit, ale cenou tohoto vylepšení paměti je výpočetní složitost, která zvyšuje provozní složitost algoritmů. [19]

Oblíbeným způsobem, jak urychlit algoritmy, které pracují s velkými poli čísel, je všemožná faktorizace . [22] Použití metod faktorizace přináší výrazné snížení provozní složitosti díky optimalizaci pole vstupních dat. [23] [22] Prstencová faktorizace se často používá pro indexové algoritmy. [23] [24] Algoritmy zvažované v tomto článku pro nalezení všech prvočísel do daného n , podobně jako síto Eratosthenes, jsou založeny na indexu, což umožňuje aplikovat na ně metodu kruhové faktorizace. [25]

Navzdory teoretickému zrychlení získanému pomocí prstencové faktorizace existují v praxi faktory, které nejsou ve výpočtech zohledněny, ale mohou mít významný vliv na chování algoritmu, který v důsledku nemusí poskytnout očekávané zvýšení rychlosti. [26] Zvažte nejvýznamnější z nich:

Násobení a dělení. V analytických výpočtech se předpokládá, že rychlost provádění aritmetických operací je ekvivalentní. Ale ve skutečnosti tomu tak není a násobení a dělení jsou mnohem pomalejší než sčítání a odčítání. Tento faktor tedy nijak neovlivňuje Eratosthenovo síto, protože používá pouze sčítání a odčítání, ale je poměrně významný pro Pitchardovo síto (jeden z výsledků výše uvedené komplikace výpočtů). [27]
Optimalizace kompilátoru. Kompilátor optimalizuje všechny programy ve fázi kompilace pro správnější provádění strojem. Často je však velmi obtížné říci, jaký přínos má daná optimalizace a zda bude tento příspěvek stejný pro dva různé algoritmy. [28]
cache . Procesor využívá cache pro urychlení načítání instrukcí a dat z paměti. Pokud máte mezipaměť, programy, které používají lokalizované odkazy, běží rychleji. Ale algoritmy třídění prvočísel, které používají vysokou faktorizaci, často generují náhodné odkazy na paměť, což snižuje jejich výkon. [28]

Pro ilustraci příspěvku faktorizace k výkonu prosévacích algoritmů jsou níže uvedeny dvě tabulky. V tabulkách jsou uvedeny výsledky měření skutečné doby provedení síta Eratosthena a síta Pitcharda v sekundách pro různé rozsahy n a různé stupně prstencové faktorizace. E i a P i jsou označení pro síto Eratosthena a Pitcharda, kde index i označuje stupeň cyklické faktorizace. E 0 a P 0 znamenají žádnou faktorizaci. [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
5000	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

Z tabulky je vidět, že nejlepší výkon má síto Eratosthenes s průměrným stupněm faktorizace E 2 . Tuto skutečnost lze vysvětlit vlivem faktoru mezipaměti diskutovaného výše na algoritmy s vysokým stupněm faktorizace.

n	P0 _	P1 _	P2 _	P3 _	P4 _	P5 _
500	0,00147	0,00074	0,00050	0,00051	0,00095	0,00649
5000	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

Jak n roste , poměr časů se stává stále více ve prospěch Eratosthenova síta a na rozsahu n = 5000000 je konzistentně rychlejší pro jakékoli faktorizace. Tato skutečnost opět potvrzuje ztrátu rychlosti Pitchardova síta v důsledku složitých výpočtů. [19]

Viz také

Poznámky

↑ Nicomachus z Gerasu , Úvod do aritmetiky , I, 13. [1]
↑ Depman I. Ya. Historie aritmetiky. Průvodce pro učitele. - M . : Education , 1965. - S. 133. - 34 000 výtisků.
↑ 12 Horsley , Rev. Samuel, FRS, " Κόσκινον Ερατοσθένους aneb, Eratosthenovo síto. Být svědectvím o jeho metodě hledání všech prvočísel," Philosophical Transactions (1683-1775), sv. 62. (1772), str. 327-347 Archivováno 2. října 2018 na Wayback Machine .
↑ Sedgewick, Robert. Algoritmy v C++ (neopr.) . - Addison-Wesley , 1992. - ISBN 0-201-51059-6 . , str. 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. ledna 1990 (použití optimalizace startu od čtverců, a tedy použití pouze čísel jehož čtverec je pod horním limitem).
↑ Pritchard, Paul, "Lineární prvočíselná síta: rodokmen", Sci. Počítat. Programování 9 :1 (1987), pp. 17-35.
↑ Přísně vzato, vnitřní smyčka se provádí pro každé prvočíslo , ale = , takže se tradičně pro stručnost odmocnina vynechává. $p\in \mathbb {P} \colon p\leq ({\sqrt {n)))$ $O(\log(\log n))$ $O(\log(\log({\sqrt {n}})))$
↑ 1 2 3 4 5 Hardy a Wright „Úvod do teorie čísel, str. 349
↑ 1 2 O'Neill, Melissa E., „The Genuine Sieve of Eratosthenes“ Archivováno 9. listopadu 2017 ve Wayback Machine , Journal of Functional Programming, publikováno online nakladatelstvím Cambridge University Press 9. října 2008 doi : 10.1017 / S0954079968
↑ 1 2 Colin Runciman, „FUNCTIONAL PEARL: Líná kolová síta a spirály prvočísel“ , Journal of Functional Programming, Volume 7 Issue 2, March 1997; také zde Archivováno 19. října 2012 na Wayback Machine .
↑ Turner, David A. Jazyková příručka SASL. Tech. rept. CS/75/1. Katedra výpočetní vědy, 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, Prvočísla: Výpočetní perspektiva , druhé vydání, Springer: 2005, str. 121-24.
↑ 1 2 3 Bays, Carterová; Hudson, Richard H. Segmentované síto Eratosthena a prvočísel v aritmetických postupech do 10 12 // BIT : journal. - 1977. - Sv. 17 , č. 2 . - str. 121-127 . - doi : 10.1007/BF01932283 .
↑ J. Sorenson, The pseudosquares prime sieve Archivováno 17. října 2012 na Wayback Machine , sborník ze 7. mezinárodního sympozia o algoritmické teorii čísel. (ANTS-VII, 2006).
↑ David Gries, Jayadev Misra. Algoritmus lineárního síta pro hledání prvočísel [1978]
↑ Peng, T.A. One Million Primes Through the Sieve , BYTE (podzim 1985), s. 243–244. Staženo 19. března 2016.
↑ 1 2 3 Paul Pritchard, Sublineární aditivní síto pro hledání prvočísel, Communications of the ACM 24 (1981), 18-23. MR : 600730
↑ 1 2 3 Paul Pritchard, Rychlá kompaktní síta prvočísel (mimo jiné), Journal of Algorithms 4 (1983), 332-344. MR : 729229
↑ 1 2 3 4 5 6 Paul Pritchard, Vysvětlování kolového síta, Acta Informatica 17 (1982), 477-485. MR : 685983
↑ 1 2 A. OL ATKIN A DJ BERNSTEIN. HLAVNÍ SÍTA POUŽÍVAJÍCÍ BINÁRNÍ KVADRATICKÉ FORMY // MATEMATIKA VÝPOČTU. Archivováno z originálu 24. prosince 2017.
↑ 1 2 Meertens, Lambert. Calculating the Sieve of Eratosthenes // Žurnál funkčního programování.
↑ 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 INDEXOVÉ ALGORITHMY PRO VÝPOČET HLAVNÍCH ČÍSEL POMOCÍ METODY PRSTENOVÉ FAKTORIZACE] // VESTNIK. - 2013. - č. 4 . - S. 29 . Archivováno z originálu 22. prosince 2017.
↑ 1 2 Jonathan Sorenson. Analýza dvou prvočíselných sít // Katedra počítačových věd University of Wisconsin-Madison. - S. 8-10 .
↑ V.A. Minajev, N.P. Vasiliev, V.V. Lukyanov, S.A. Nikonov, D.V. Nikerov. [ http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf INDEXOVÉ ALGORITHMY PRO VÝPOČET HLAVNÍCH ČÍSEL POMOCÍ METODY PRSTENOVÉ FAKTORIZACE] // VESTNIK. - 2013. - č. 4 . - S. 30-31 . Archivováno z originálu 22. prosince 2017.
↑ V.A. Minajev, N.P. Vasiliev, V.V. Lukyanov, S.A. Nikonov, D.V. Nikerov. [ http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf INDEXOVÉ ALGORITHMY PRO VÝPOČET HLAVNÍCH ČÍSEL POMOCÍ METODY PRSTENOVÉ FAKTORIZACE] // VESTNIK. - 2013. - č. 4 . - S. 30-33 . Archivováno z originálu 22. prosince 2017.
↑ Jonathan Sorenson. Analýza dvou prvočíselných sít // Katedra počítačových věd University of Wisconsin-Madison. - S. 16-18 .
↑ Jonathan Sorenson. Analýza dvou prvočíselných sít // Katedra počítačových věd University of Wisconsin-Madison. - S. 16 .
↑ 1 2 3 Jonathan Sorenson. Analýza dvou prvočíselných sít // Katedra počítačových věd University of Wisconsin-Madison. - S. 17 .

Literatura

Síto Eratosthenes // Elokventia - Yaya. - M. : Sovětská encyklopedie, 1957. - S. 141. - ( Velká sovětská encyklopedie : [v 51 svazcích] / šéfredaktor B. A. Vvedensky ; 1949-1958, v. 49).
Galperin G. "Jen o prvočíslech" // Kvant . - 1987. - č. 4 . - S. 10-14 :38 .
Nepublikované materiály L. Eulera o teorii čísel / Ruská akademie věd , Ústav dějin přírodních věd a techniky , St. Petersburg. Phil.; Comp. Matvievskaya G.P. [atd.]; Rep. vyd. Něvskaja N.I. - Petrohrad. : Nauka , 1997. - ISBN 5-02-024847-9 .
Prof. D.F. Egorov. Prvky teorie čísel . - Státní nakladatelství Moskva, 1923. (nepřístupný odkaz)
Kordemsky B. A. Matematická vynalézavost . - M. : GIFML, 1958. - 576 s.

Odkazy

Slovníky a encyklopedie	Velká dánština Brockhaus a Efron chorvatský Britannica (online) Brockhaus