fork download
copy 
  1. #include <chrono>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. const int MAXN = 100000;
  9.  
  10. template <int N>
  11. struct Sieve {
  12.     bool is_prime[N];
  13.     constexpr Sieve() : is_prime() {
  14.         for (int i = 2; i < N; i++) {
  15.             is_prime[i] = true;
  16.         }
  17.         for (int i = 2; i < N; i++)
  18.             if (is_prime[i]) {
  19.                 for (int j = 2 * i; j < N; j += i) {
  20.                     is_prime[j] = false;
  21.                 }
  22.             }
  23.     }
  24. };
  25.  
  26. bool fast_is_prime(int n) {
  27.     static constexpr Sieve<MAXN> s;
  28.     return s.is_prime[n];
  29. }
  30.  
  31. bool slow_is_prime(int n) {
  32.     return (Sieve<MAXN>{}).is_prime[n];
  33. }
  34.  
  35. bool alt_slow_is_prime(int n) {
  36.     return (Sieve<MAXN>()).is_prime[n];
  37. }
  38.  
  39. bool alt2_slow_is_prime(int n) {
  40.     Sieve<MAXN> dynamic;
  41.     return dynamic.is_prime[n];
  42. }
  43.  
  44. const int reps = 1000;
  45. int main() {
  46.     vector<int> numbers(reps);
  47.     for (int i = 0; i < reps; i++) {
  48.         numbers[i] = rand() % MAXN;
  49.     }
  50.  
  51.     int ans = 0;
  52.     auto t1 = chrono::high_resolution_clock::now();
  53.     for (auto &n : numbers) {
  54.         ans += slow_is_prime(n);
  55.     }
  56.     auto t2 = chrono::high_resolution_clock::now();
  57.     cout <<  "Time taken by sieve<MAXN>{}).is_prime[n]: " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;   
  58.  
  59.  
  60.     ans = 0;
  61.     t1 = chrono::high_resolution_clock::now();
  62.     for (auto &n : numbers) {
  63.         ans += alt_slow_is_prime(n);
  64.     }
  65.     t2 = chrono::high_resolution_clock::now();
  66.     cout << "Time taken by sieve<MAXN>().is_prime[n]: " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;
  67.  
  68.     ans = 0;
  69.     t1 = chrono::high_resolution_clock::now();
  70.     for (auto &n : numbers) {
  71.         ans += alt2_slow_is_prime(n);
  72.     }
  73.     t2 = chrono::high_resolution_clock::now();
  74.     cout << "Time taken by sieve<MAXN> dynamic: " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;
  75.  
  76.     ans = 0;
  77.     t1 = chrono::high_resolution_clock::now();
  78.     for (auto &n : numbers) {
  79.         ans += fast_is_prime(n);
  80.     }
  81.     t2 = chrono::high_resolution_clock::now();
  82.     cout << "Time taken by constexpr sieve<MAXN> s: " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;
  83. }
Success #stdin #stdout 0.78s 4448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Time taken by sieve<MAXN>{}).is_prime[n]: 376
Time taken by sieve<MAXN>().is_prime[n]: 405
Time taken by sieve<MAXN> dynamic: 0
Time taken by constexpr sieve<MAXN> s: 0
https://ideone.com/GiGvRj
language:
C++14 (gcc 8.3)
created:
3 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!