Ciurul lui Eratostene(det. tuturor nr prime

[AnaKonD]

Nu stiu cat de mult va folosi chestia aceasta unora dintre care probabil stiti deja dar mie mi'a fost de un real folos la probleme si cred ca ar putea fi extins domeniul de aplicatie al acestui algoritm (inca ma gandesc).Sa incepem .

Se da spre exemplu urmatoarea problema:

Fie n un numar natural(n<=10000).Sa se genereze toate numerele prime mai mici decat n.

Ok.Primul lucru la care m'am gandit cand am auzit chestia asta a fost sa generez toate numerele < n si sa vad daca sunt prime.Dar imediat mi'am dat seama ca este o idee proasta.Pentru 9999 de numere algoritmul ar fi stat o vesnicie(figurativ vb).Apoi am spus ca mai trebuie sa existe si alta cale.Si exista.Se numeste Ciurul lui Eratostene.

Eratostene a fost un important matematician si filozof al Antichitatii.Desi putine dintre lucraile lui s'au pastrat,a ramas celebru prin metoda rapida de determinare a numerelor prime si prin faptul ca a fost primul care a estimat cu acuratete diametrul Pamantului.

Ideea este de a "pune in ciur" toate numerele mai mici decat n,apoi de a "cerne" aceste numere pana raman in ciur numai numere prime.Mai intai "cernem"(eliminam di ciur) toti multiplii lui 2,apoi multiplii lui 3 s.a.m.d.Vom reprezenta ciurul ca un vector cu 10000 de componente care pot fi 0 sau 1,cu semnificatia ciur=0,daca este in ciur,si 1,altfel(in carte era invers dar ar mai fi necesitat o operatie in plus pt ca vectorul daca l'am declarat global era deja initilizat cu 0;daca am fi pus invers ar fi trebuit sa mai facem si :

Cod:

for(i=0;i ).Haideti sa vedem si algoritmul cum arata :

Cod:

#include

using namespace std;

int i,j,n,k;
int ciur[10000];


int main()
{
    cout<<"Introduceti limita multimii: ";
    cin>>n;

    for(i=2;i<=(n/2);i++)
      for(j=2;(j*i)<=n;j++)
        ciur[j*i]=1;
    for(i=2;i      if(ciur[i]==0)
        cout<    cout<<'n';
    system("PAUSE");
    return 0;
}            

Acesta a fost algoritmul meu facut in Dev-CPP.Cel dat in manual spune asa :

Cod:

#include
#define NMax 10000
int main()
{
  int ciur[NMax],n,i,j;
  cout<<"n= ";
  cin>>n;
  for(i=2;i    ciur[i]=1;
  for(i=2;i*i<=n;i++)
    if(ciur[i])
      for(j=2;j*i         ciur[i*j]=0;
  for(i=2;i    if(ciur[i])
      cout<  return 0;
}

 Iar in cazul in care doriti sa gasiti toate numerele prime dintr'un interval puteti proceda asa:

Cod:

#include

using namespace std;

int a,i,j,n;
int v[10000];


int main()
{
    cout<<"Introduceti intervalele multimii: "<<'n';
    cout<<"Inceput: ";
    cin>>a;
    cout<<"Sfarsit: ";
    cin>>n;

    for(i=a;i<=(n/2);i++)
      for(j=2;(j*i)<=n;j++)
        v[j*i]=1;
    for(i=a;i      if(v[i]==0)
        cout<    cout<<'n';
    system("PAUSE");
    return 0;
}            

De asemeni scris in Dev-CPP.Sper sa va fie de folos .Daca aveti completari,intrebari,observatii,etc  va rog sa le scrieti aici. :thleft:

[AdyX]

Poate este cineva interesat si de varianta Pascal a acestui algoritm :whistle:

Cod:

var i, j: word;
      ciur: array[1..64000] of byte;
begin
  writeln('Introduceti limita multimii');
  readln(n);
  for i:=1 to n do
      ciur[i]:=1;
  for i:=2 to n div 2 do
    for j:=2 to n div i do
      ciur[i*j]:=0;
  for i:=3 to n do
    if ciur[i]=1 then
      write(i, ' ');
  readln;
end.

[SkullAds]