fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 1e8 + 5;
  6. bool sieve[MAXN];
  7. vector<int> primes;
  8. void calc() {
  9.     for (int i = 3; i < MAXN; i += 2) {
  10.         if (!sieve[i])
  11.             primes.push_back(i);
  12.         for (int j = 0; j < primes.size() && i * primes[j] < MAXN; j++) {
  13.             sieve[primes[j] * i] = true;
  14.             if (i % primes[j] == 0)
  15.                 break;
  16.         }
  17.     }
  18. }
  19. bitset<MAXN> sieve2;
  20. vector<int> primes2;
  21. void calc2() {
  22.     int i = 3;
  23.     for (; i * i < MAXN; i += 2) {
  24.         if (sieve2[i])
  25.             continue;
  26.  
  27.         primes2.push_back(i);
  28.         for (int j = i * i; j < MAXN; j += 2 * i)
  29.             sieve2[j] = true;
  30.     }
  31.     while (i < MAXN) {
  32.         if (!sieve2[i])
  33.             primes2.push_back(i);
  34.         i += 2;
  35.     }
  36. }
  37. unsigned int prime[MAXN / 64];
  38. #define gP(n) (prime[n >> 6] & (1 << ((n >> 1) & 31)))
  39. #define rP(n) (prime[n >> 6] &= ~(1 << ((n >> 1) & 31)))
  40. bool checkPrime(int x) { return (x & 1) && gP(x); }
  41. vector<int> primes3;
  42. void calc3() {
  43.     memset(prime, -1, sizeof(prime));
  44.  
  45.     for (int i = 3; i * i < MAXN; i += 2)
  46.         if (gP(i)) {
  47.             for (unsigned int j = i * i; j < MAXN; j += 2 * i)
  48.                 rP(j);
  49.         }
  50.     for (int i = 2; i < MAXN; i++)
  51.         if (checkPrime(i))
  52.             primes3.push_back(i);
  53. }
  54.  
  55. const int MAX_PR = MAXN;
  56. bitset<MAX_PR> isprime;
  57. vector<int> primes4;
  58. void calc4(int lim) {
  59.     isprime.set();
  60.     isprime[0] = isprime[1] = 0;
  61.     for (int i = 4; i < lim; i += 2)
  62.         isprime[i] = 0;
  63.     for (int i = 3; i * i < lim; i += 2)
  64.         if (isprime[i])
  65.             for (int j = i * i; j < lim; j += i * 2)
  66.                 isprime[j] = 0;
  67.     vector<int> pr;
  68.     for (int i = 2; i < lim; i++)
  69.         if (isprime[i])
  70.             primes4.push_back(i);
  71.     return;
  72. }
  73.  
  74. int sieve5[MAXN];
  75. vector<int> primes5;
  76. int itr2 = 0;
  77. void calc5() {
  78.     for (int i = 3; i < MAXN; i += 2) {
  79.         if (!sieve5[i])
  80.             primes5.push_back(i);
  81.         for (int j = 0; j < primes5.size() && i * primes5[j] < MAXN; j++) {
  82.             sieve5[primes5[j] * i] = primes5[j];
  83.             if (primes5[j] == sieve5[i])
  84.                 break;
  85.         }
  86.     }
  87. }
  88. signed main() {
  89.     ios::sync_with_stdio(0);
  90.     cin.tie(0);
  91.     clock_t begin;
  92.     begin = clock();
  93.     calc();
  94.     cout << "linear sieve: " << (double)(clock() - begin) / CLOCKS_PER_SEC << ' ' << primes.size() << endl;
  95.     begin = clock();
  96.     calc2();
  97.     cout << "nonlinear sieve: " << (double)(clock() - begin) / CLOCKS_PER_SEC << ' ' << primes2.size() << endl;
  98.     begin = clock();
  99.     calc3();
  100.     cout << "bitset: " << (double)(clock() - begin) / CLOCKS_PER_SEC << ' ' << primes3.size() << endl;
  101.     begin = clock();
  102.     calc4(MAXN);
  103.     cout << "kth: " << (double)(clock() - begin) / CLOCKS_PER_SEC << ' ' << primes4.size() << endl;
  104.     begin = clock();
  105.     calc5();
  106.     cout << "linear sieve v2: " << (double)(clock() - begin) / CLOCKS_PER_SEC << ' ' << primes5.size() << endl;
  107. }
Success #stdin #stdout 2.17s 534016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
linear sieve: 0.400509 5761454
nonlinear sieve: 0.425846 5761454
bitset: 0.291533 5761454
kth: 0.549361 5761455
linear sieve v2: 0.505507 5761454
https://ideone.com/z11b4t
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!