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.     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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
old: 1.09915
new: 0.545811
segmented_sieve: 0.295204
https://ideone.com/d8mlsS
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!