Search This Blog

Sunday, July 1, 2012

C++: Ciurul lui Eratostene

Ciurul lui Eratostene este o metoda de verificare a numerelor daca sunt prime, destul de lenta si foarte limitata la matematica, dar cea mai rapida la informatica, in cazul in care se cere verificarea proprietatii de prim pentru mai multe numere. In cazul a mai putin de 10 numere se foloseste algoritmul clasic: Verificarea lui "n" daca este prim (varianta clasica).
TEORIA:
Pasul 1: Cream un sir de numere consecutive (de la 2) pana la maximul posibil precizat in restrictiile problemei.
Pasul 2: Incepem cu primul numar (2) si intr-un sir auxiliar cu exact atatea elemente ca primul (in care initial toate sunt 0) marcam multiplii numarului, prin transformarea in 1 a valorilor corespunzatoare acestora, din al IIlea sir.
Pasul 3: Luam urmatorul numar pentru care valoarea sa din al IIlea sir este 0 si repetam pasul 2 pentru numarul respectiv.
Pasul 4: .......
Dupa aplicarea pasului 3 pana la sfarsitul sirului principal, toate numerele care inca mai au corespondenta din sirul al IIlea egala cu 0 sunt prime.
ALGORITMUL: pentru formarea sirului al IIlea, cel cu 0 si 1. In codul informatic, acesta este singurul sir practic, primul imaginandu-se numai pe pozitiile lui.
d=2;
uc=sqrt(1 000 000);
while(d<=uc) {
          for(i=2; i<=uc/i; i++)
                       ciur[d*i]=1;

          d++;
          while(ciur[d]==1)
                       d++;
}