Ciurul lui Erathostene

Ciurul lui Eratostene

h1. Ciurul lui Erathostene

h1. Ciurul lui Eratostene

(Creat de ==user(user="Cosmin" type="tiny")== la data de _2004-11-24_ 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 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

  }
==

Urmatoarea optimizare va fi marcarea multiplilor numarului prim $i$ de la $i*i$ nu de la $2*i$ cum am facut in prima varianta sau de la $3*i$ cum am facut in a {$2$}-a. Aceasta optimizare este evidenta: orice numar prim compus multiplu de $i$ mai mic decat $i*i$ are un factor prim mai mic decat {$i$}, si acel factor l-a marcat mai devreme, deci nu are rost sa il marcam si la pasul {$i$}. Ideea aceasta este exact ideea ce se foloseste la rezolvarea problemei "Numere Prime":http://www.infoarena.ro/task/prim din arhiva infoarena. Sa vedem acum codul sursa:

Urmatoarea optimizare va fi marcarea multiplilor numarului prim $i$ de la $i*i$ nu de la $2*i$ cum am facut in prima varianta sau de la $3*i$ cum am facut in a {$2$}-a. Aceasta optimizare este evidenta: orice numar prim compus multiplu de $i$ mai mic decat $i*i$ are un factor prim mai mic decat {$i$}, si acel factor l-a marcat mai devreme, deci nu are rost sa il marcam si la pasul {$i$}. Ideea aceasta este exact ideea ce se foloseste la rezolvarea problemei "Numere Prime":problema/prim din arhiva infoarena. Sa vedem acum codul sursa:

== code(java) |
  //class PrimeNumbersSieve4

  final int MAXSIZE = 100000000/2/8+1;
  char[] p = new char[MAXSIZE];

  //p[i] == 0 if 2*i + 1 is prime

  //(p[i>>3]&(1<<(i&7))) == 0 if 2*i + 1 is prime

  public int getTheNumber(int n) {
    int i, j, nr = 1;

3682