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.

  1	2	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.

  1	2	3	4	5
  6	7	8	9	10
  11	12	13	14	15
  16	17	18	19	20
  21	22	23	24	25

  • •  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:

  1	2	3	4	5
  6	7	8	9	10
  11	12	13	14	15
  16	17	18	19	20
  21	22	23	24	25

  • •  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.

  1	2	3	4	5
  6	7	8	9	10
  11	12	13	14	15
  16	17	18	19	20
  21	22	23	24	25

  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.