fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. struct timeit {
  8.     decltype(chrono::high_resolution_clock::now()) begin;
  9.     const string label;
  10.     timeit(string label = "???") : label(label) { begin = chrono::high_resolution_clock::now(); }
  11.     ~timeit() {
  12.         auto end = chrono::high_resolution_clock::now();
  13.         auto duration = chrono::duration_cast<chrono::milliseconds>(end - begin).count();
  14.         cerr << duration << "ms elapsed [" << label << "]" << endl;
  15.     }
  16. };
  17. const int MAXN = 2e8;
  18.  
  19.  
  20.  
  21. namespace newkactl {
  22. #define rep(i, a, b) for (int i = a; i < (b); ++i)
  23. #define trav(a, x) for (auto &a : x)
  24. #define all(x) begin(x), end(x)
  25. #define sz(x) (int)(x).size()
  26. typedef long long ll;
  27. typedef pair<int, int> pii;
  28. typedef vector<int> vi;
  29.  
  30. const int LIM = MAXN;
  31.  
  32. vi eratosthenes() {
  33.     const int S = round(sqrt(LIM)), h = (LIM - 1) / 2;
  34.     vi pr({2}), sieve(S + 1);
  35.     vector<array<int, 2>> cp;
  36.     for (int i = 3; i < S; i += 2) {
  37.         if (sieve[i])
  38.             continue;
  39.         cp.push_back({i, i * i / 2 - 1});
  40.         for (int j = i * i; j <= S; j += 2 * i)
  41.             sieve[j] = true;
  42.     }
  43.     for (int l = 1; l <= h; l += S) {
  44.         array<bool, S> block{};
  45.         trav(i, cp) {
  46.             int idx = i[1];
  47.             for (; idx < S; idx += i[0])
  48.                 block[idx] = true;
  49.             i[1] = idx - S;
  50.         }
  51.         rep(i, 0, min(S, h - l)) if (!block[i]) pr.push_back((l + i) * 2 + 1);
  52.     };
  53.     return pr;
  54. }
  55. } // namespace newkactl
  56.  
  57. namespace pajene {
  58. typedef long long ll;
  59. const int NMAX = MAXN;
  60. bitset<NMAX / 2> bits;
  61. vector<int> sieve() {
  62.     bits.set();
  63.     vector<int> primes({2});
  64.     for (int i = 3; (i >> 1) < bits.size(); i = 2 * bits._Find_next(i >> 1) + 1) {
  65.         primes.push_back(i);
  66.         // i is prime >= 3
  67.         for (ll j = (ll)i * i >> 1; j < bits.size(); j += i)
  68.             bits[j] = 0;
  69.     }
  70.     return primes;
  71. }
  72. } // namespace pajene
  73.  
  74. namespace kactl {
  75. #define rep(i, a, b) for (int i = a; i < (b); ++i)
  76. #define trav(a, x) for (auto &a : x)
  77. #define all(x) begin(x), end(x)
  78. #define sz(x) (int)(x).size()
  79. typedef long long ll;
  80. typedef pair<int, int> pii;
  81. typedef vector<int> vi;
  82. const int MAX_PR = MAXN;
  83. bitset<MAX_PR> isprime;
  84. vi eratosthenesSieve() {
  85.     int lim = MAX_PR;
  86.     isprime.set();
  87.     isprime[0] = isprime[1] = 0;
  88.     for (int i = 4; i < lim; i += 2)
  89.         isprime[i] = 0;
  90.     for (int i = 3; i * i < lim; i += 2)
  91.         if (isprime[i])
  92.             for (int j = i * i; j < lim; j += i * 2)
  93.                 isprime[j] = 0;
  94.     vi pr;
  95.     rep(i, 2, lim) if (isprime[i]) pr.push_back(i);
  96.     return pr;
  97. }
  98. } // namespace kactl
  99.  
  100. template <class F> void bench(string name, F f) {
  101.     timeit x(name);
  102.     f();
  103. }
  104. signed main() {
  105.     ios::sync_with_stdio(0);
  106.     cin.tie(0);
  107.     clock_t begin;
  108.     bench("newkactl", newkactl::eratosthenes);
  109.     bench("bitset", pajene::sieve);
  110.     bench("kactl", kactl::eratosthenesSieve);
  111. }
Success #stdin #stdout #stderr 2.76s 107304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
366ms elapsed [newkactl]
802ms elapsed [bitset]
1610ms elapsed [kactl]
https://ideone.com/U6DOdm
language:
C++ (gcc 8.3)
created:
8 days 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!