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. 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. void segmented_sieve() {
  41. int n = N;
  42. const int S = 10000;
  43.  
  44. primes.clear();
  45. vector<int> Ps;
  46. int nsqrt = sqrt(n);
  47. vector<char> is_prime(nsqrt + 1, true);
  48. for (int i = 2; i <= nsqrt; i++) {
  49. if (is_prime[i]) {
  50. Ps.push_back(i);
  51. for (int j = i * i; j <= nsqrt; j += i)
  52. is_prime[j] = false;
  53. }
  54. }
  55.  
  56. int result = 0;
  57. vector<char> block(S);
  58. for (int k = 0; k * S <= n; k++) {
  59. fill(block.begin(), block.end(), true);
  60. int start = k * S;
  61. for (int p : Ps) {
  62. int start_idx = (start + p - 1) / p;
  63. int j = max(start_idx, p) * p - start;
  64. for (; j < S; j += p)
  65. block[j] = false;
  66. }
  67. if (k == 0)
  68. block[0] = block[1] = false;
  69. for (int i = 0; i < S && start + i <= n; i++) {
  70. if (block[i])
  71. primes.push_back(start+i);
  72. }
  73. };
  74. }
  75.  
  76. int main()
  77. {
  78. auto t0 = clock();
  79. oldsieve();
  80. auto t1 = clock();
  81. auto primes_old = primes;
  82. primes.clear();
  83. cout << "old: " << (1.0 * (t1 - t0)) / CLOCKS_PER_SEC << endl;
  84.  
  85. t0 = clock();
  86. newsieve();
  87. t1 = clock();
  88. auto primes_new = primes;
  89. primes.clear();
  90. cout << "new: " << (1.0 * (t1 - t0)) / CLOCKS_PER_SEC << endl;
  91. assert(primes_new == primes_old);
  92.  
  93. t0 = clock();
  94. segmented_sieve();
  95. t1 = clock();
  96. auto primes_seg = primes;
  97. primes.clear();
  98. cout << "segmented_sieve: " << (1.0 * (t1 - t0)) / CLOCKS_PER_SEC << endl;
  99. assert(primes_seg == primes_old);
  100. }
Success #stdin #stdout 1.96s 112896KB
stdin
Standard input is empty
stdout
old: 1.09915
new: 0.545811
segmented_sieve: 0.295204