fork(2) 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. 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
stdin
Standard input is empty
stdout
diff is 1.12477
diff is 0.584102