Vizualizare sursă pentru „Ciurul lui Eratostene”

[[Imagine:Sieve_of_Eratosthenes_animation.gif|right|Ciurul lui Eratostene]]
În [[matematică]], '''ciurul lui Eratostene''' este un [[algoritm]] simplu și vechi de descoperire a tuturor [[Număr prim|numerelor prime]] până la un [[Număr întreg|întreg]] specificat. Este predecesorul algoritmului modern ''[[ciurul lui Atkin]]'', un algoritm mai rapid dar mai complex. A fost creat de [[Eratostene]], un [[matematician]] din [[Grecia antică]].

==Algoritm==
# Se scrie o listă a numerelor de la 2 la cel mai mare număr ce urmează a fi testat pentru primalitate. Numim această listă ''lista A''. (Lista de pătrate din partea stângă a imaginii.)
# Se trece numărul 2, primul număr prim găsit, într-o altă listă, cea a numerelor prime găsite. Numim această listă ''lista B''. (Este lista din partea dreaptă a imaginii.)
# Se marchează 2 și toți [[multiplu|multiplii]] lui 2 din lista A.
# Primul număr nemarcat din listă este un număr prim. Se trece acest număr în lista B.
# Se marchează acest număr și toți multiplii lui din lista A. Marcarea de multipli poate să înceapă de la pătratul numărului, întrucât multiplii mai mici au fost deja marcați în pașii anteriori.
# Se repetă pașii 4 și 5 până când se epuizează toate numerele din lista A.

== Complexitatea algoritmului și alte detalii ==

Marcarea multiplilor unui număr prim poate începe de la pătratul acelui număr, deoarece multiplii mai mici au fost deja marcați.

[[Teoria complexității|Complexitatea]] în timp a algoritmului este de <math>O(n \log \log n)</math> și cea în spațiu este de <math>O(n)</math>.<ref>{{Citat carte|author=Pritchard, Paul|title=Linear prime-number sieves: a family tree|publisher=Sci. Comput. Programming'' '''9''':1 (1987)|pages=17–35}}</ref> Versiunea segmentată a ciurului lui Eratostene, cu optimizări elementare, cum ar fi factorizarea pe roată, utilizează <math>O(n)</math> operațiuni și <math>O(n^{1/2}\log\log n/\log n)</math> biți de memorie.<ref>{{Citat web|author=A. O. L. Atkin și D. J. Bernstein|url=http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf|title=Prime sieves using binary quadratic forms|publisher=Mathematics of Computation'' '''73''' (2004)|pages=1023–1030}}</ref>

[[David Turner]] a sugerat în 1975 ca ciurul lui Eratostene să fie reprezentat într-o modalitate simplă și elegantă într-un [[Programare funcțională|limbaj de programare funcțională]].<ref>{{citat carte|author=Turner, David A.|title=SASL language manual. Tech. rept. CS/75/1.|publisher=Department of Computational Science, Universitatea St. Andrews|year=1975}}</ref>
Ciurul lui Turner, redat în [[Limbajul de programare Haskell|Haskell]], este:

 prime = ciur [2..]
 ciur (p : xs) = p : ciur [x | x <− xs, x ‘mod‘ p > 0]

Totuși, [[Melissa O'Neill]]
<ref>O'Neill, Melissa E., [http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=2428392&fulltextType=RA&fileId=S0956796808007004ER "The Genuine Sieve of Eratosthenes"], Journal of Functional Programming, Published online by Cambridge University Press 9 octombrie 2008 doi:10.1017/S0956796808007004.</ref>
a arătat că complexitatea implementării funcționale a lui Turner este semnificativ mai mare decât cea a implementărilor în limbaje imperative.

==Note==
<references />
{{Portal|Matematică}}

[[Categorie:Aritmetică]]
[[Categorie:Algoritmi]]
[[Categorie:Numere prime]]