Sita lui Eratosthenes

Sita lui Eratosthenes  este un algoritm pentru găsirea tuturor numerelor prime până la un număr întreg n , care este atribuit matematicianului grec antic Eratosthenes din Kirensky [1] . Ca în multe cazuri, aici denumirea algoritmului vorbește despre principiul funcționării acestuia, adică sita implică filtrarea , în acest caz, filtrarea tuturor numerelor cu excepția celor prime. Pe măsură ce parcurgeți lista, numerele necesare rămân, iar cele inutile (se numesc compuse ) sunt excluse.

Istorie

Această metodă este descrisă în „Introducere în aritmetică” de Nicomachus din Geras . Nicomachus îl numește pe Eratostene drept autorul metodei . Iamblichus face același lucru în comentariul său asupra acestei lucrări a lui Nicomah.

Numele de „sită” a fost dat metodei deoarece pe vremea lui Eratostene scriau numere pe o tăbliță acoperită cu ceară și făceau găuri în acele locuri în care erau scrise numere compuse . Așadar, tăblița era un fel de sită prin care erau „cernute” toate numerele compuse și rămâneau doar numere prime [2] .

Algoritm

Pentru a găsi toate numerele prime nu mai mari decât un număr dat n , urmând metoda lui Eratostene, trebuie să efectuați următorii pași:

  1. Scrieți pe rând toate numerele întregi de la doi la n (2, 3, 4, ..., n ).
  2. Fie variabila p inițial egală cu doi, primul număr prim.
  3. Taiați numerele de la 2 p la n din listă, numărând în pași de p (aceștia vor fi multipli de p : 2 p , 3 p , 4 p , …).
  4. Găsiți primul număr neîncrucișat din listă care este mai mare decât p și atribuiți valoarea lui p acelui număr.
  5. Repetați pașii 3 și 4 cât mai mult timp posibil.

Acum toate numerele neîncrucișate din listă sunt toate numere prime de la 2 la n .

În practică, algoritmul poate fi îmbunătățit după cum urmează. În pasul #3, numerele pot fi tăiate, începând imediat cu p 2 , deoarece toți multiplii mai mici ai lui p au în mod necesar un divizor prim mai mic decât p și sunt deja tăiați până la acest moment. Și, în consecință, algoritmul poate fi oprit când p 2 devine mai mare decât n . [3] În plus, toate numerele prime cu excepția lui 2 sunt impare, deci pot fi considerate trepte de 2 p , începând cu p 2 .

Exemplu pentru n = 30

Să scriem numere naturale, începând de la 2 la 30 la rând:

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

Primul număr din listă, 2  este prim. Să parcurgem o serie de numere, tăind toate numerele care sunt multipli ai lui 2 (adică în fiecare secundă, începând cu 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

Următorul număr neîncrucișat, 3 ,  este prim. Să parcurgem o serie de numere, tăind toate numerele care sunt multipli ai lui 3 (adică fiecare treime, începând cu 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

Următorul număr neîncrucișat, 5 ,  este prim. Să parcurgem o serie de numere, tăind toți multiplii lui 5 (adică fiecare cincime, începând cu 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

Următorul număr neîncrucișat este 7 . Pătratul său, 49 ,  este mai mare decât 30 , așa că asta este. Toate numerele compuse sunt deja tăiate:

2 3 5 7 11 13 17 19 23 29

Pseudocod

Implementare optimizată (începând cu pătrate) în pseudocod [4] [5] :

Intrare : număr natural n Ieșire : toate numerele prime de la 2 la n . Fie A o matrice booleană indexată cu numere de la 2 la n , populate initial cu valori adevarate . pentru i  := 2, 3, 4, ... în timp ce i 2 ≤ n : dacă A [ i ] = adevărat : pentru j  := i 2 , i 2 + i , i 2 + 2 i , ..., în timp ce j ≤ n : atribuie A [ j ] := fals return : toate numerele i pentru care A [ i ] = adevărat .

Complexitatea algoritmului

Complexitatea algoritmului echivalează cu operații în compilarea unui tabel de numere prime până la [6] .

Dovada complexității

Când este selectat , pentru fiecare prim , se va executa o buclă interioară [7] , care va efectua acțiuni. Complexitatea algoritmului poate fi obținută din estimarea următoarei valori:

Deoarece numărul de numere prime mai mici sau egal cu este evaluat ca și, în consecință, al-lea număr prim este aproximativ egal cu , atunci suma poate fi convertită:

Aici, sumandu-ul pentru primul număr prim este separat de sumă pentru a evita împărțirea la zero. Această sumă poate fi estimată prin integrală

Rezultatul este pentru suma inițială:

O dovadă mai riguroasă (și care oferă o estimare mai precisă până la factorii constanți) poate fi găsită în „An Introduction to the Theory of Numbers” a lui Hardy și Wright [8] .

Modificări de metodă

Variație nelimitată, graduală

În această variantă, numerele prime se calculează secvenţial, fără limită superioară, [9] ca numere dintre numerele compuse, care se calculează pentru fiecare număr prim p , începând de la pătratul său, cu un pas de p (sau pentru numerele prime impare ). 2p ) [3] . Poate fi reprezentat simbolic în paradigma fluxului de date ca

prime = [ 2 ..] \ [[ p² , p² + p ..] pentru p în numere prime ]

folosind notația de abstractizare a listei , unde \denotă diferența dintre progresiile aritmetice .

Primul număr prim 2 (dintre numerele întregi pozitive crescătoare ) este cunoscut dinainte, deci nu există un cerc vicios în această definiție autoreferențială .

Pseudo-cod pentru cernerea treptată, într-un mod ineficient, pentru simplitate, implementare (comparați cu următoarele opțiuni):

prime = sita [ 2.. ] unde sita [ p , ... xs ] = [ p , ... sita ( xs \ [ p² , p² + p ..])]

Enumerarea divizorilor

Sita lui Eratosthenes este adesea confundată cu algoritmi care filtrează numerele compuse pas cu pas , testând fiecare dintre numerele candidate pentru divizibilitate folosind un număr prim la fiecare pas. [zece]

Cunoscutul cod funcțional al lui David Turner în 1975 [11] este adesea confundat cu sita lui Eratosthenes, [10] dar de fapt [9] aceasta este o variantă suboptimă cu enumerarea divizorilor (în varianta optimă, divizori mai mari decât rădăcina pătrată a numărului testat nu sunt utilizate). În pseudocod,

prime = sită [ 2.. ] unde sită [ p , ... xs ] = [ p , ... sită [ x în xs dacă x%p > 0 ]]

Sita segmentata

După cum notează Sorenson, principala problemă cu implementarea site-ului lui Eratosthenes pe computere nu este numărul de operațiuni efectuate, ci cerințele pentru cantitatea de memorie ocupată (cu toate acestea, observația sa se referă la computerul acum învechit DEC VAXstation 3200, lansat în 1989). [5] Pentru valori mari ale lui n , intervalul primelor poate depăși memoria disponibilă; mai rău, chiar și pentru n relativ mic , utilizarea memoriei cache este departe de a fi optimă, deoarece algoritmul, trecând prin întregul tablou, încalcă principiul localizării referințelor .

Pentru rezolvarea problemei prezentate se folosește o sită segmentată, în care doar o parte din intervalul primelor este cernută pe iterație. [12] Această metodă este cunoscută încă din anii 1970 și funcționează după cum urmează: [5] [13]

  1. Împărțim intervalul de la 2 la n în segmente (segmente) de o anumită lungime Δ ≤ √ n .
  2. Găsim toate numerele prime din primul segment folosind o sită obișnuită.
  3. Fiecare dintre segmentele următoare se termină la un număr m . Găsim toate numerele prime din segment după cum urmează:
    1. Creați o matrice booleană de dimensiune
    Δ
  4. Pentru fiecare număr prim p ≤ √ m dintre cele deja găsite, notăm în tablou ca „neprim” toate numerele care sunt multiple ai p , sortând numerele cu pas de p , începând de la cel mai mic multiplu al numărului p . în acest segment.

Dacă numărul Δ este ales să fie √ n , atunci complexitatea de memorie a algoritmului este estimată a fi O ( √ n ) , iar complexitatea operațională rămâne aceeași cu cea a site-ului convențional al lui Eratosthenes. [13]

Pentru cazurile în care n este atât de mare încât toate primele cernute mai mici decât √ n nu pot încăpea în memorie, așa cum este cerut de algoritmul de sită segmentată, mai lent, dar cu cerințe de memorie mult mai mici, se folosesc algoritmi, cum ar fi sita Sorenson . [paisprezece]

sita lui Euler

Dovada identității lui Euler pentru funcția zeta Riemann conține un mecanism de filtrare a numerelor compuse similare cu sita lui Eratostene, dar în așa fel încât fiecare număr compus să fie eliminat din listă o singură dată. O sită similară este descrisă în Gries & Misra 1978 ca o sită în timp liniară (vezi mai jos ).

Lista inițială este întocmită pornind de la numărul 2 . La fiecare etapă a algoritmului, primul număr din listă este luat ca următor număr prim, rezultatele produsului al căruia cu fiecare număr din listă sunt marcate pentru eliminarea ulterioară. După aceea, primul număr și toate numerele marcate sunt eliminate din listă, iar procesul se repetă din nou:

[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 7 6 7 7 6 7 7 6 7 6 [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 ... [...]

Iată un exemplu care începe cu numere impare, după primul pas al algoritmului. Astfel, după pasul k -al, lista de lucru conține numai coprime cu primele k prime (adică numere care nu sunt multiple ale niciunuia dintre primele k prime) și începe cu (k+1) -al-lea prim. Toate numerele din listă mai mici decât pătratul primului său număr sunt prime.

În pseudocod,

prime = sita [ 2.. ] unde sita [ p , ... xs ] = [ p , ... sita ( xs \ [ p² , ... p * xs ])]

Ciur numai pentru numere impare

Deoarece toate numerele pare, cu excepția lui 2, sunt compuse, este posibil să nu procesați deloc numerele pare, ci să operați numai cu numere impare. În primul rând, va reduce la jumătate cantitatea de memorie necesară. În al doilea rând, va reduce numărul de operații efectuate de algoritm (la jumătate).

În pseudocod:

prime = [2, ...sită [ 3,5.. ]] unde sită [ p , ... xs ] = [ p , ... sită ( xs \ [ p² , p² + 2p ..])]

Acest lucru poate fi generalizat la numere coprime nu numai cu 2 (adică numere impare), ci și cu 3, 5 etc.

Reducerea cantității de memorie consumată

Algoritmul lui Eratosthenes operează de fapt pe biți de memorie . Prin urmare, puteți economisi în mod semnificativ consumul de memorie prin stocarea variabilelor de tip boolean nu ca octeți , ci ca biți, adică octeți de memorie.

Această abordare – „compresie de biți” – complică funcționarea acestor biți. Orice citire sau scriere a unui bit va reprezenta mai multe operații aritmetice . Dar, pe de altă parte, compactitatea în memorie este îmbunătățită semnificativ. Intervalele mari se încadrează în memoria cache, care funcționează mult mai rapid decât de obicei, așa că atunci când se lucrează pe segmente, viteza totală crește.

Sita lui Eratosthenes cu timp de rulare liniar

Acest algoritm găsește pentru fiecare număr i din intervalul [2...n] divizorul prim minim lp[i] ( lp reprezintă cel mai mic prim ) . 

De asemenea, este acceptată o listă cu toate numerele prime, matricea pr[] , inițial goală. În cursul algoritmului, această matrice va fi completată treptat.

Inițial, toate valorile lp[i] vor fi umplute cu zerouri.

Apoi, repetă peste numărul curent i de la 2 la n . Pot fi două cazuri aici:

Prin urmare, trebuie să atribuim lp[i] = i și să adăugăm i la sfârșitul listei pr[] .

În ambele cazuri, începe procesul de aranjare a valorilor în matricea lp[i] : ar trebui să luați numere care sunt multipli ai lui i și să le actualizați valoarea lp[] . Totuși, scopul principal este să înveți cum să o faci în așa fel încât, în final, fiecare număr să aibă valoarea lp[] cel mult o dată.

Se susține că acest lucru se poate face în acest fel. Se consideră numere de forma x = p ⋅ i , unde p este succesiv egal cu toate numerele prime care nu depășesc lp[i] (doar pentru aceasta a fost necesar să se păstreze o listă a tuturor numerelor prime).

Pentru toate numerele de acest fel, punem o nouă valoare lp[x]  - ar trebui să fie egală cu p [15] .

Pseudocod Intrare : număr natural n Fie pr un tablou întreg, inițial gol; lp - tablou întreg, indexat de la 2 la n , completat cu zerouri pentru i  := 2, 3, 4, ..., până la n : dacă lp [ i ] = 0 : lp [ i ] := i pr [] += { i } pentru p de pr în timp ce p ≤ lp [ i ] şi p*i ≤ n : lp [ p*i ] := p Ieșire : toate numerele din tabloul pr .

Complexitatea algoritmului în practică

Sita lui Eratosthenes este o modalitate populară de a evalua performanța computerului. [16] După cum se poate observa din demonstrația de mai sus a complexității algoritmului, scăpând de constantă și de termenul foarte aproape de zero (ln (ln n - ln ln n ) - ln ln 2 ≈ ln ln n ) , complexitatea temporală a calculării tuturor numerelor prime mai mici decât n este aproximată prin următoarea relație O ( n ln ln n ) . Cu toate acestea, algoritmul are o complexitate de timp exponențială în raport cu dimensiunea intrării, făcându-l un algoritm pseudopolinom . Memoria necesară pentru algoritmul de bază este O ( n ) . [17]

Versiunea segmentată are aceeași complexitate operațională O ( n ln ln n ) , [8] . ca versiunea nesegmentată, dar reduce amprenta de memorie necesară la dimensiunea unui segment (dimensiunea unui segment este mult mai mică decât dimensiunea întregii matrice de numere prime), care este O (√ n /ln  n ) . [18] Există, de asemenea, o sită segmentată optimizată de Eratosthenes, care este foarte rar în practică. Este construit în O ( n ) operații și ia O ( √n ln ln n /ln n ) biți de memorie. [17] [19] [18]

În practică, se dovedește că estimarea lui ln ln n nu este foarte precisă chiar și pentru intervalele practice maxime precum 10 16 . [19] Făcând cunoștință cu dovada de complexitate de mai sus , nu este greu de înțeles de unde provine inexactitatea estimării. Discrepanța cu estimarea poate fi explicată astfel: în acest interval practic de cernere, deplasările constante au un efect semnificativ. [8] Astfel, termenul cu creștere foarte lentă ln ln n nu devine suficient de mare pentru ca constantele să fie destul de neglijate până când n se apropie de infinit, care este în mod natural în afara limitelor în orice interval de cernere aplicat. [8] Acest fapt arată că, pentru datele de intrare curente, performanța sitei lui Eratosthenes este mult mai bună decât ne-am aștepta folosind doar estimări asimptotice ale complexității timpului. [19]

Sita lui Eratosthenes este mai rapidă decât sita Atkin , des comparată, numai pentru valori de n mai mici de 10 10 . [20] Acest lucru este adevărat presupunând că operațiunile durează aproximativ același timp în cicluri CPU , ceea ce este o presupunere rezonabilă pentru un singur algoritm care funcționează pe un bitmap uriaș. [21] Având în vedere această ipoteză, se pare că sita Atkin este mai rapidă decât sita maximă factorizată a lui Eratosthenes pentru n peste 10 13 , dar astfel de intervale de cernere ar necesita o cantitate uriașă de spațiu RAM chiar dacă s-ar folosi „ambalarea biților”. [21] Totuși, secțiunea despre versiunea segmentată a sitei lui Eratosthenes arată că ipoteza menținerii egalității în timpul petrecut la o operație între cei doi algoritmi nu este satisfăcută de segmentare. [13] [20] La rândul său, acest lucru face ca sita Atkin (ne-segmentată) să funcționeze mai lent decât sita segmentată a lui Eratosthenes cu o rază de cernere crescândă, cu prețul unui timp redus pe operație pentru a doua.

Utilizarea notației O mare nu este, de asemenea, modalitatea corectă de a compara performanța practică chiar și pentru variațiile site-ului lui Eratosthenes, deoarece această notație ignoră constantele și offset-urile, care pot fi foarte semnificative pentru domeniile de aplicare. [8] De exemplu, o variantă a sitei lui Eratosthenes cunoscută sub numele de sită Pritchard [17] are performanță O ( n ) , [19] dar implementarea ei de bază necesită fie algoritmul „one big array” [18] (adică, folosind o matrice obișnuită, în care stochează toate numerele până la n ), care își limitează domeniul de utilizare la cantitatea de memorie disponibilă sau trebuie să fie segmentată pentru a reduce utilizarea memoriei. Lucrarea lui Pritchard a redus la limită cerințele de memorie, dar costul acestei îmbunătățiri a memoriei este complexitatea de calcul, care crește complexitatea operațională a algoritmilor. [19]

O modalitate populară de a accelera algoritmii care funcționează cu rețele mari de numere este tot felul de factorizare . [22] Utilizarea metodelor de factorizare dă o reducere semnificativă a complexității operaționale datorită optimizării matricei de date de intrare. [23] [22] Factorizarea inelului este adesea folosită pentru algoritmii de index. [23] [24] Algoritmii luați în considerare în acest articol pentru găsirea tuturor primelor până la un n dat , asemănătoare cu sita lui Eratostene, sunt bazați pe indici, ceea ce face posibilă aplicarea metodei factorizării inelare. [25]

În ciuda accelerației teoretice obținute prin factorizarea inelului , în practică există factori care nu sunt luați în considerare în calcule, dar pot avea un impact semnificativ asupra comportamentului algoritmului, care, ca urmare, poate să nu dea creșterea așteptată a performanței. [26] Luați în considerare cele mai semnificative dintre ele:

  • Înmulțirea și împărțirea. În calculele analitice, se presupune că viteza de efectuare a operațiilor aritmetice este echivalentă. Dar, de fapt, nu este cazul, iar înmulțirea și împărțirea sunt mult mai lente decât adunarea și scăderea. Astfel, acest factor nu afectează în niciun fel sita lui Eratosthenes, deoarece folosește doar adunarea și scăderea, dar este destul de semnificativ pentru sita Pitchard (unul dintre rezultatele complicației calculelor menționate mai sus). [27]
  • Optimizarea compilatorului. Compilatorul optimizează toate programele în etapa de compilare pentru o execuție mai corectă de către mașină. Dar este adesea foarte dificil de spus ce contribuție aduce o anumită optimizare și dacă această contribuție va fi aceeași pentru doi algoritmi diferiți. [28]
  • cache . Procesorul folosește un cache pentru a accelera recuperarea instrucțiunilor și a datelor din memorie. Având un cache, programele care folosesc link-uri localizate să ruleze mai rapid. Dar algoritmii de sortare a numerelor prime care folosesc factorizarea ridicată generează adesea referințe aleatorii de memorie, ceea ce le reduce performanța. [28]

Pentru a ilustra contribuția factorizării la performanța algoritmilor de cernere, sunt prezentate mai jos două tabele. Tabelele arată rezultatele măsurării timpului real de execuție al sitei lui Eratosthenes și al sitei lui Pitchard în secunde pentru diferite intervale de n și diferite grade de factorizare inelă. E i și P i sunt denumirile pentru sita lui Eratosthenes și respectiv Pitchard, unde indicele i denotă gradul de factorizare inelă. E 0 și P 0 înseamnă că nu există factorizare. [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
50000 0,05156 0,03281 0,02617 0,02578 0,03164 0,10663
500000 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

Din tabel se poate observa că sita lui Eratostene cu un grad mediu de factorizare E 2 are cea mai bună performanţă . Acest fapt poate fi explicat prin influența factorului cache discutat mai sus asupra algoritmilor cu un grad ridicat de factorizare.

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
50000 0,15507 0,08203 0,05664 0,04843 0,04180 0,04413
500000 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

Pe măsură ce n crește , raportul de timp devine din ce în ce mai mult în favoarea sitei lui Eratosthenes, iar pe intervalul n = 5000000 este constant mai rapid pentru orice factorizări. Acest fapt confirmă încă o dată pierderea de viteză a sitei Pitchard din cauza calculelor complexe. [19]

Vezi și

Note

  1. ↑ Nicomachus din Gheras , Introducere în aritmetică , I, 13. [1]
  2. ↑ Depman I. Ya. Istoria aritmeticii. Un ghid pentru profesori. - M . : Educaţie , 1965. - S. 133. - 34.000 exemplare.
  3. ↑ 12 Horsley , Rev. Samuel, FRS, " Κόσκινον Ερατοσθένους sau, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers ", Philosophical Transactions (1683-1775), voi. 62. (1772), pp. 327-347 Arhivat 2 octombrie 2018 la Wayback Machine .
  4. ↑ Sedgewick, Robert. Algoritmi în C++  (neopr.) . - Addison-Wesley , 1992. - ISBN 0-201-51059-6 . , p. 16.
  5. ↑ 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 ianuarie 1990 (utilizarea optimizării pornind de la pătrate și, astfel, folosind numai numerele al cărui pătrat este sub limita superioară, este prezentat).
  6. ↑ Pritchard, Paul, „Linear prime-number sieves: a family tree”, Sci. Calculator. Programare 9 :1 (1987), pp. 17-35.
  7. ↑ Strict vorbind, bucla interioară este efectuată pentru fiecare prim , dar = , deci, în mod tradițional, pentru concizie, rădăcina pătrată este omisă.
  8. ↑ 1 2 3 4 5 Hardy și Wright „O introducere în teoria numerelor, p. 349
  9. ↑ 1 2 O'Neill, Melissa E., „The Genuine Sieve of Eratosthenes” Arhivat la 9 noiembrie 2017 la Wayback Machine , Journal of Functional Programming, publicat online de Cambridge University Press 9 octombrie 2008 doi : 10.1017/S0956796808007 .
  10. ↑ 1 2 Colin Runciman, „FUNCTIONAL PEARL: Lazy wheel sieves and spirals of primes” , Journal of Functional Programming, volumul 7, numărul 2, martie 1997; tot aici Arhivat 19 octombrie 2012 la Wayback Machine .
  11. ↑ Turner, David A. Manual de limbă SASL. Teh. rept. CS/75/1. Departamentul de Științe Computaționale, Universitatea 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)
  12. ↑ Crandall & Pomerance, Prime Numbers: A Computational Perspective , ediția a doua, Springer: 2005, pp. 121-24.
  13. ↑ 1 2 3 Bays, Carter; Hudson, Richard H. The segmented sieve of Eratosthenes and primes in aritmetic progressions to 10 12  //  BIT : journal. - 1977. - Vol. 17 , nr. 2 . - P. 121-127 . - doi : 10.1007/BF01932283 .
  14. ↑ J. Sorenson, The pseudosquares prime sieve Arhivat la 17 octombrie 2012 la Wayback Machine , Proceedings of the 7th International Symposium on Algorithmic Number Theory. (FURCI-VII, 2006).
  15. ↑ David Gries, Jayadev Misra. Un algoritm de sită liniară pentru găsirea numerelor prime [1978]
  16. ↑ Peng, T.A. One Million Primes Through the Sieve , BYTE  (toamna 1985), pp. 243–244. Preluat la 19 martie 2016.
  17. ↑ 1 2 3 Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18-23. MR : 600730
  18. ↑ 1 2 3 Paul Pritchard, Situri de numere prime compacte rapide (printre altele), Journal of Algorithms 4 (1983), 332-344. MR : 729229
  19. ↑ 1 2 3 4 5 6 Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477-485. MR : 685983
  20. ↑ 1 2 A. OL ATKIN ȘI DJ BERNSTEIN. SITE PRIME FOLOSIND FORME CADRATICE BINARE  // MATEMATICA CALCULUI. Arhivat din original pe 24 decembrie 2017.
  21. ↑ 1 2 Meertens, Lambert. Calcularea sită a lui Eratosthenes // Jurnal de programare funcțională.
  22. ↑ 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 ALGORITMI DE INDEX PENTRU CALCULUL NUMERELOR PRIME FOLOSIND METODA DE FACTORIZARE INELULUI] // VESTNIK. - 2013. - Nr 4 . - S. 29 . Arhivat din original pe 22 decembrie 2017.
  23. ↑ 1 2 Jonathan Sorenson. O analiză a două site-uri cu numere prime  // Departamentul de informatică Universitatea din Wisconsin-Madison. - S. 8-10 .
  24. ↑ V.A. Minaev, N.P. Vasiliev, V.V. Lukyanov, S.A. Nikonov, D.V. Nikerov. [ http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf ALGORITMI DE INDEX PENTRU CALCULUL NUMERELOR PRIME FOLOSIND METODA DE FACTORIZARE INELULUI] // VESTNIK. - 2013. - Nr 4 . - S. 30-31 . Arhivat din original pe 22 decembrie 2017.
  25. ↑ V.A. Minaev, N.P. Vasiliev, V.V. Lukyanov, S.A. Nikonov, D.V. Nikerov. [ http://vestnik-rosnou.ru/pdf/n4y2013/p29.pdf ALGORITMI DE INDEX PENTRU CALCULUL NUMERELOR PRIME FOLOSIND METODA DE FACTORIZARE INELULUI] // VESTNIK. - 2013. - Nr 4 . - S. 30-33 . Arhivat din original pe 22 decembrie 2017.
  26. ↑ Jonathan Sorenson. O analiză a două site-uri cu numere prime  // Departamentul de informatică Universitatea din Wisconsin-Madison. - S. 16-18 .
  27. ↑ Jonathan Sorenson. O analiză a două site-uri cu numere prime  // Departamentul de informatică Universitatea din Wisconsin-Madison. - S. 16 .
  28. ↑ 1 2 3 Jonathan Sorenson. O analiză a două site-uri cu numere prime  // Departamentul de informatică Universitatea din Wisconsin-Madison. - S. 17 .

Literatură

Link -uri

  Accesați articolul Wikidata  Dicționare și enciclopedii