RSS

Ciurul lui Eratostene – sirul numerelor prime

12 Dec

Definitii

  • Un numar se numeste prim daca nu are alti divizori in afara de el si 1.
  • Un numar prim are 2 divizori.
  • Un numar neprim se numeste divizibil.

Problema 1. Sa se determine numerele prime pana la N.

Problema 2. Sa se determine primele N numere prime.

Evident exista si alte probleme ce necesita lucrul cu mai multe valori prime (descompunerea in factori primi, … ).

De aceasta problema, a determinarii primelor numere prime, s-a ocupat si Eratostene, cel care a dat si metoda care ii poarta numele: ciurul lui Eratostene. El a realizat o matrice 10*10 in care a marcat numerele pana la 100. Apoi a luat, pe rand, fiecare valoare (nemarcata) incepand cu 2 si a marcat (sters) multiplii ei. Au ramas nemarcate tocmai numerele prime pentru ca, asa cum spune definitia lor, nu au nici un divizor.

Din punct de vedere al optimizarii procesuli de calcul, putem determina mai usor sirul numerelor prime pana la N decat sa cercetam fiecare valoare in parte daca este prima sau nu.

METODA 1

Daca incercam implementarea algoritmul lui Eratostene (numerele prime pana la 100), rezolvam practic problema 1. Fiecare valoare C[I] din vector va avea valoarea 1 (daca I este prim), respectiv 0 daca I este divizibil.

int C[100], N, I, J;

cin>>N;

for(I=1;I<=N; I++) C[I] =1;

for (I=2;i<=N;I++)

    if(C[I] == 1) // I este prim => multiplii pana la N vor fi zero

         for(J=2;J*I <= N;J ++)  C[I*J] = 0;

//afisarea numerelor prime

for(I=1;I<=N; I++)

    if(C[I] ==1) cout <<I<< “este prim”<<endl;

Gratie vectorului generat, putem afirma intr-un singur pas daca o valoare X este numar prim sau nu: C[X]==1 ?

METODA 2

S-ar putea ca o problema sa doreasca numai numerele prime, ca in cazul descompunerii in factori primi sau a problemei 2.

O metoda de a construi un vector format numai din numere prime (evident in ordine crescatoare) ar putea fi urmatoarea. Algoritmul porneste de la observatia ca daca un numar nu are divizori printre numerele prime mai mici decat el, atunci este un numar prim.

int C[100], NC, I, J;

//2 este primul numar prim

C[1]=2; NC=1; cin >>N;

for(I=3; NC<N; I=I+2) //merg doar pe numere impare

{//caut divizori pentru I

for(J=1;J<=NC && I % C[J]!=0 ;J++);

if(J>NC) //nu s-a gasit divizor=> I este prim si il adaug la sfarsitul vectorului

{NC++; C[NC]=I;}

}

//ies cand NC==N

//afisez primele N numere prime

for(I=1;I<=N;I++) cout<<C[I]<<” “;

 

Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: