fork(1) download
  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
stdin
Standard input is empty
stdout
diff is 0.659061
diff is 0.633464