Ciurul lui Erathostene

Ciurul lui Eratostene

h1. Ciurul lui Erathostene

h1. Ciurul lui Eratostene

(Creat de '_Cosmin_':user/Cosmin 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.

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

    for (i = 1; (i << 1) + 1 <= n; i += 1) {
      if (p[i] == 0) {
        nr++;

        for (j = i + i + i + 1;
 
               (j << 1) + 1 <= n;
 
                  j += (i << 1) + 1) {

        for (j = i + i + i + 1; (j << 1) + 1 <= n; j += (i << 1) + 1) {

          p[j] = 1;
        }
      }

  }
==

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

      }
    }
    for (i=1; 2 * i + 1 <= n; ++i)

        if (p[i] == 0) nr++;
    return nr;
  }

  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;

    for (i = 1;
 
         ((i * i) << 1) + (i << 1) <= n;
 
          i += 1) {

    for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1) {

      if ((p[i >> 3] & (1 << (i & 7))) == 0) {

        for (j = ((i * i) << 1) + (i << 1);
 
              (j << 1) + 1 <= n;
 
               j += (i << 1) + 1) {

        for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1) {

          p[j >> 3] |= (1 << (j & 7));
        }
      }
    }
    for (i = 1; 2 * i + 1 <= n; ++i)

         if ((p[i >> 3] & (1 << (i & 7))) == 0)

             nr++;
    return nr;
  }

Se pare ca optimizarile codului initial au dus la o imbunatatire a vitezei cu un factor de {$10$}.

Problemele sugerate la inceputul articolului sunt destul de frumoase si ar trebui rezolvate. Pentru fiecare dintre ele puteti sa va testati rezolvarea: la algoritmus sunt disponibile fisierele de intrare si iesire, infoarena si uva au evaluatoare automate si pentru problema de pe TOPCODER puteti intra in applet-ul lor si sa incercati sa o rezolvati in practice roomul asociat SRM-ului 190 dupa ce o rezolvati folositi optiunea Run System Test din Practice Room Options.

Problemele sugerate la inceputul articolului sunt destul de frumoase si ar trebui rezolvate. Pentru fiecare dintre ele puteti sa va testati rezolvarea: la algoritmus sunt disponibile fisierele de intrare si iesire, infoarena si uva au evaluatoare automate si pentru problema de pe "TOPCODER":http://www.topcoder.com/tc puteti intra in applet-ul lor si sa incercati sa o rezolvati in practice roomul asociat SRM-ului 190 dupa ce o rezolvati folositi optiunea Run System Test din Practice Room Options.

3682