Ciurul lui Eratostene

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
Ciurul lui Eratostene

În matematică, ciurul lui Eratostene este un algoritm simplu și vechi de descoperire a tuturor numerelor prime până la un î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[modificare | modificare sursă]

  1. 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.)
  2. 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.)
  3. Se marchează 2 și toți multiplii lui 2 din lista A.
  4. Primul număr nemarcat din listă este un număr prim. Se trece acest număr în lista B.
  5. 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.
  6. Se repetă pașii 4 și 5 până când se epuizează toate numerele din lista A.

Complexitatea algoritmului și alte detalii[modificare | modificare sursă]

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

Complexitatea în timp a algoritmului este de O(n \log \log n) și cea în spațiu este de O(n).[1] Versiunea segmentată a ciurului lui Eratostene, cu optimizări elementare, cum ar fi factorizarea pe roată, utilizează O(n) operațiuni și O(n^{1/2}\log\log n/\log n) biți de memorie.[2]

David Turner a sugerat în 1975 ca ciurul lui Eratostene să fie reprezentat într-o modalitate simplă și elegantă într-un limbaj de programare funcțională.[3] Ciurul lui Turner, redat în Haskell, este:

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

Totuși, Melissa O'Neill [4] 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[modificare | modificare sursă]

  1. ^ Pritchard, Paul. Linear prime-number sieves: a family tree. Sci. Comput. Programming 9:1 (1987). pp. 17–35 
  2. ^ A. O. L. Atkin și D. J. Bernstein. „Prime sieves using binary quadratic forms”. Mathematics of Computation 73 (2004). pp. 1023–1030. http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf. 
  3. ^ Turner, David A. (1975). SASL language manual. Tech. rept. CS/75/1.. Department of Computational Science, Universitatea St. Andrews 
  4. ^ O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 9 octombrie 2008 doi:10.1017/S0956796808007004.