(Creat de '_Cosmin_':user/Cosmin la data de _2004-11-24_ categoria _Teoria numerelor_, autor(i) _Cosmin_)
*Continut scurt:*

 ==Include(page="template/raw")==
 
Articolul de fata incearca o implementarea mai eficienta a acestui algoritm clasic. Se poate optimiza pentru a folosi doar O(sqrt(n)) memorie, varianta prezentata aici folosind O(n / log n) memorie, unde log n e numarul de biti al unui cuvant.

 Articolul de fata incearca o implementarea mai eficienta a acestui algoritm clasic. Se poate optimiza pentru a folosi doar O(sqrt(n)) memorie, varianta prezentata aici folosind O(n / log n) memorie, unde log n e numarul de biti al unui cuvant.

*Continut lung:*

==Include(page="template/raw")==
 

Ciurul lui Erathostene e un algoritm clasic care se invata la scoala impreuna cu conceptul de numere prime inca din clasa a 6. Acest algoritm determina toate numerele prime mai mici decat un numar dat ca parametru. Ideea lui de abordare a acestei probleme poate fi modificata pentru a rezolva si alte probleme precum problema Fractii din arhiva infoarena, problema Riemann vs Mertens din arhiva uva ([1]http://acm.uva.es/p/v107/10738.html), problema Divizibilitate a rundei 4 a concursului algoritmus ([2]http://algoritmus.org/probleme/Probleme_Runda04.php), sau problema Square Free a SRM-ului 190 de pe TOPCODER ([3]http://www.topcoder.com/stat?c=problem_statement&pm=2342&rd=4770, rezolvarea ei o gasiti aici : [4]http://www.topcoder.com/index?t=statistics&c=srm190_prob) . (linkurile ce contin litere mari nu merg pentru ca editorul le trasforma automat in litere mici si nu mai pot fi modificate, daca vreti sa urmati un link faceti un copy paste cu adresa in browserul vostru)
In articolul acesta nu ne vom concentra asupra acestor probleme ci asupra implementarii optimizate ale algoritmului original.