Question

Ati putea sa-mi explicati implememtatia ciurului lui eratostene in c++, in detaliu?
(incepand cu o versiune simpla si neompimizata, trepat adaugand optimizari, la o versiune a algoritmului mult mai optimizata)

(am gasit odata asa ceva pe internet si acum nu o pot gasi)
(cred ca asta e singura modalitate pentru a-mi reaminti Ciurul)

Answer 1

#include <fstream>  /// Programul numara cate numere prime sunt in intervalul [1,n]

#define NN 1000000

ifstream fin("eratostene.in");

ofstream fout("eratostene.out");

int n, v[NN];

int main(){

v[0] = v[1] = 1;   /// 0 si 1 nu sunt prime (le marcam cu 1

for(int i=2;i*i<NN; ++i)

 if(v[i]==0)  /// daca v[i] e marcat ca fiind prim i

  for(int j=2;i*j<NN;++j)

   v[i*j] = 1;  /// i*j fiind produs de numere intregi (i si j), marcam v[i*j] cu 1 (adica i*j nu e prim)

fin >> n;

int x,C = 0;

for(int i=1;i<=n;++i){

 fin >> x;

 if(v[x]==0)

  C ++;

}

fout << C;

return 0;

}