Ciurul lui Eratostene

Pentru început, să rezolvăm următoarea problemă:

Se întroduc de la tastatură n numere naturale mai mici decât 1.000.000. Determinați câte dintre acestea sunt prime.

Exemplu de intrare:

10
2 5 7 12 16 18 568 569 677 655

Exemplu de ieșire:

5

O idee de rezolvare ar fi parcurgerea fiecărui număr din șir verificând dacă acesta este prim:

  1.  Presupunem că numărul este prim.
  2.  Verificăm cazurile particulare:
    • 0 și 1 nu sunt prime.
    • Singurul număr prim par este 2.
  3.  Dacă numărul nu îndeplinește unul dintre cazurile de mai sus,căutăm un divizor parcurgând intervalul \([2,\sqrt{n}]\). La găsirea unui divizor, marcăm numărul ca fiind compus.

Realizăm însă că această metodă este ineficientă, pentru fiecare număr verificându-se cazurile particulare și determinând divizorii acestuia.

O soluție mult mai eficientă constă în utilizarea ciurului lui Eratostene. Algoritm provenit din Antichitate determină numerele prime mai mici sau egale cu o valoare dată. Alegerea acestei valori depinde atât de cerințele cât și de restricțiile problemei ce încercăm să o rezolvăm.

Algoritmul

  1.  Se scrie o listă a numerelor de la 1 până la valoarea aleasă.
  2.  Se marchează 1 ca fiind număr compus (conform teoremei fundamentale a aritmeticii)
  3.  Se trece la primul număr prim găsit, 2. Se marchează multiplii acestuia ca fiind numere compuse.
  4.  Se caută următorul număr prim, marcându-se multplii acestuia ca fiind numere compuse.
  5.  Se continuă pasul 4 până când se epuizează toate numerele din listă.

Să aplicăm algoritmul pentru a afla numerele prime până la 25. Marcarea multiplilor unui număr prim poate începe de la pătratul acestuia:

      •  Scriem toate numerele până la 25. Marcăm numărul 1, acesta nefiind prim.
    12345
    678910
    1112131415
    1617181920
    2122232425
      •  Trecem la primul număr prim, 2. Vom marca toți multiplii săi.
    12345
    678910
    1112131415
    1617181920
    2122232425
      •  Observăm că următorul număr nemarcat este 3. Tăiem multiplii săi (unii deja au fost tăiați fiindcă sunt și multiplii ai numărului 2:
    12345
    678910
    1112131415
    1617181920
    2122232425
      •  Luăm următorul număr prim, 5. De asemenea, 5*5=25 deci căutarea poate înceta. Toate numerele care au fost tăiate sunt compuse.
    12345
    678910
    1112131415
    1617181920
    2122232425

    Implementarea algoritmului

Pentru stocarea rezultatelor vom folosi un vector caracteristic cu următoarea semnificație:

\(ciur[n] = 0\), dacă n este prim.

\(ciur[n] = 1\), dacă n nu este prim (numărul a fost marcat).

#define NMAX 1000001
//NMAX - valoarea pana la care dorim sa determinam numerele prime.

//Declaram de tip bool.
//1 - nu este prim;
//0 - este prim

bool ciur[NMAX];

void Eratostene()
{
    ciur[0]=ciur[1]=1; //0 si 1 nu sunt prime
    for(int i=2; i*i<=NMAX; i++)
    {
        if(ciur[i]==0)
            for(int j=2; j<=NMAX/i; j++)
                ciur[i*j]=1; //Marcam multiplii
    }
}

 

 

Animație a Ciurului lui Eratostene în graphics.h

Codul sursă îl găsiți aici.

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Acest site folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.

iulie 2018
L Ma Mi J V S D
 1
2345678
9101112131415
16171819202122
23242526272829
3031