fork(5) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e8;
  4. bool comp[N];
  5. vector<int>primes;
  6. void oldsieve()
  7. {
  8.     memset(comp,0,sizeof comp);
  9.     primes.clear();
  10.  
  11.     bool done = false;
  12.     for(int i=2;i<N;i++)
  13.         if(!comp[i])
  14.         {
  15.             primes.push_back(i);
  16.  
  17.             if (i * i > N) {
  18.             	done = true;
  19.             }
  20.  
  21.             if (!done) for(int j=i*i;j<N;j+=i)
  22.                 comp[j]=1;
  23.         }
  24. }
  25. void newsieve()
  26. {
  27.     memset(comp,0,sizeof comp);
  28.     primes.clear();
  29.     for(int i=2;i<N;i++)
  30.     {
  31.         if(!comp[i])
  32.             primes.push_back(i);
  33.             for(int j=0,si=primes.size();j<si&&i*primes[j]<N;j++)
  34.             {
  35.                 comp[primes[j]*i]=1;
  36.                 if(i%primes[j]==0)break;
  37.             }
  38.     }
  39. }
  40. int main()
  41. {
  42. 	auto t0 = clock();
  43.     oldsieve();
  44.     //for(int i=0;i<20;i++)cout<<primes[i]<<' ';cout<<endl;
  45.     auto mid = clock();
  46.     cout << "diff is " << (1.0 * (mid - t0)) / CLOCKS_PER_SEC << endl;
  47.     newsieve();
  48.     //for(int i=0;i<20;i++)cout<<primes[i]<<' ';cout<<endl;
  49.     cout << "diff is " << (1.0 * (clock() - mid)) / CLOCKS_PER_SEC << endl;
  50. }
Success #stdin #stdout 1.71s 112896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
diff is 1.12477
diff is 0.584102
https://ideone.com/HMjE7c
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!