fork(2) 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.     vector<bool> p(N+1, true);
  12.  
  13.     for(int i=4; i<N; i+=2)
  14. 		p[i]=false; // erasing the even number
  15. 	for(int i=3; i*i<N; i+=2) { //computing only odd number
  16. 		if (p[i]) { //if i is prime then
  17. 			for(int j=i*i; j<N; j=j+i+i) { // erasing only odd number which is composite
  18. 				p[j]=false;
  19. 			}
  20. 		}
  21. 	}
  22.  
  23. 	// If you erase this you will get even faster
  24. 	for (int i=2; i < N; ++i)
  25. 		if (p[i])
  26. 			primes.push_back(i);
  27. }
  28. void newsieve()
  29. {
  30.     memset(comp,0,sizeof comp);
  31.     primes.clear();
  32.     for(int i=2;i<N;i++)
  33.     {
  34.         if(!comp[i])
  35.             primes.push_back(i);
  36.             for(int j=0,si=primes.size();j<si&&i*primes[j]<N;j++)
  37.             {
  38.                 comp[primes[j]*i]=1;
  39.                 if(i%primes[j]==0)break;
  40.             }
  41.     }
  42. }
  43. int main()
  44. {
  45. 	auto t0 = clock();
  46.     oldsieve();
  47.     //for(int i=0;i<20;i++)cout<<primes[i]<<' ';cout<<endl;
  48.     auto mid = clock();
  49.     cout << "diff is " << (1.0 * (mid - t0)) / CLOCKS_PER_SEC << endl;
  50.     newsieve();
  51.     //for(int i=0;i<20;i++)cout<<primes[i]<<' ';cout<<endl;
  52.     cout << "diff is " << (1.0 * (clock() - mid)) / CLOCKS_PER_SEC << endl;
  53. }
Success #stdin #stdout 1.3s 146052KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
diff is 0.659061
diff is 0.633464
https://ideone.com/NB3fYR
language:
C++14 (gcc 8.3)
created:
3 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!