fork(10) 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. const int reps = 1000;
  36. int main() {
  37.     vector<int> numbers(reps);
  38.     for (int i = 0; i < reps; i++) {
  39.         numbers[i] = rand() % MAXN;
  40.     }
  41.  
  42.     int ans = 0;
  43.     auto t1 = chrono::high_resolution_clock::now();
  44.     for (auto &n : numbers) {
  45.         ans += slow_is_prime(n);
  46.     }
  47.     auto t2 = chrono::high_resolution_clock::now();
  48.     cout << "Runtime ans: " << ans << ". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;
  49.  
  50.     ans = 0;
  51.     t1 = chrono::high_resolution_clock::now();
  52.     for (auto &n : numbers) {
  53.         ans += fast_is_prime(n);
  54.     }
  55.     t2 = chrono::high_resolution_clock::now();
  56.     cout << "Compiletime ans: " << ans << ". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;
  57. }
Success #stdin #stdout 0.41s 4268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Runtime ans: 95. Elapsed (ms): 406
Compiletime ans: 95. Elapsed (ms): 0
https://ideone.com/YcRdB8
language:
C++14 (gcc 8.3)
created:
4 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!