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 655Exemplu de ieșire:
5
O idee de rezolvare ar fi parcurgerea fiecărui număr din șir verificând dacă acesta este prim:
- Presupunem că numărul este prim.
- Verificăm cazurile particulare:
- 0 și 1 nu sunt prime.
- Singurul număr prim par este 2.
- 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
- Se scrie o listă a numerelor de la 1 până la valoarea aleasă.
- Se marchează 1 ca fiind număr compus (conform teoremei fundamentale a aritmeticii)
- Se trece la primul număr prim găsit, 2. Se marchează multiplii acestuia ca fiind numere compuse.
- Se caută următorul număr prim, marcându-se multplii acestuia ca fiind numere compuse.
- 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.
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 -
- Trecem la primul număr prim, 2. Vom marca toți multiplii săi.
12 3 45 67 89 1011 1213 1415 1617 1819 2021 2223 2425 -
- 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:
12 3 45 67 891011 1213 14151617 1819 20212223 2425 -
- 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.
12 3 45 67 891011 1213 14151617 1819 20212223 2425Implementarea 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.