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.

==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":http://acm.uva.es/p/v107/10738.html din arhiva "uva":http://acm.uva.es/, problema "Divizibilitate":http://algoritmus.org/probleme/Probleme_Runda04.php a rundei 4 a concursului algoritmus, sau problema "Square Free":http://www.topcoder.com/stat?c=problem_statement&pm=2342&rd=4770 a SRM-ului 190 de pe TOPCODER, rezolvarea ei o gasiti "aici":http://www.topcoder.com/index?t=statistics&c=srm190_prob.
In articolul acesta nu ne vom concentra asupra acestor probleme ci asupra implementarii optimizate ale algoritmului original.