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:

3 responses to “Ciurul lui Eratostene – sirul numerelor prime

  1. roxana

    16/06/2015 at 17:51

    Buna ziua! As dori si eu un algoritm de verificare a unui nr daca estet patrat perfect..pe internet nu am gasit ceva care sa ma ajute..Doar asta care nu o inteleg : cout<>n;
    if (sqrt(n)==(int)(sqrt(n)))
    cout<<n<<" este patrat perfect "<<endl;
    else
    cout<<n<<" nu este patrat perfect "<<endl;

    Multumesc anticipat!

     
  2. mchelariu71

    17/06/2015 at 07:45

    testul verifica daca radicalul numarului N este un numar fara zecimale, adica un numar intreg/natural -> daca partea intreaga a radicalului este radicalul insusi.

     
  3. melania

    08/07/2015 at 18:54

    Buna ziua! Cum afisez primele n nr.prime unde n este dat, in pseudocod? Multumesc.

     

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: