h1. Ciurul lui Erathostene
h1. Ciurul lui Eratostene
(Categoria _Teoria numerelor_, autor(i) _Cosmin_)
(Categoria _Matematica_, Autor _Cosmin Negruseri_)
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.
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":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.
Ciurul lui Eratostene 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":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.
Am mai scris despre aceste optimizari intr-un articol din ginfo, dar codul de acolo nu era testat si nu merge :).
Ideea la acest algoritm e ca marcam intr-un sir fiecare multiplu al unui numar prim si numerele ramase nemarcate sunt numere prime, o descriere mai grafica gasiti la "adresa":http://mathworld.wolfram.com/SieveofEratosthenes.html.
Sa incercam o prima implementare a acestui algoritm (implementarile vor folosi limbajul java, dar sunt foarte usor transformabile in C/C++).
Sa incercam o prima implementare a acestui algoritm (implementarile vor folosi limbajul Java, dar sunt foarte usor transformabile in C/C++).
== code(java) |
//class PrimeNumbersSieve1
