fork(4) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <chrono>
  5. #include <cmath>
  6. using namespace std;
  7. typedef uint32_t uint;
  8.  
  9. //////////////////////////////////////////////////////////////////////////////
  10. struct Task
  11. {   uint result;
  12.     Task(uint n) : result(0)
  13.     {   for(uint i = 1; i < n; i +=2)
  14.             if(is_simple(i))
  15.                 result++;
  16.     }
  17.     bool is_simple(uint n)
  18.     {   for(uint i = 3; i <= sqrt(n); i +=2)
  19.             if(n%i == 0)
  20.                 return false;
  21.         return true;
  22.     }
  23. };
  24.  
  25. //////////////////////////////////////////////////////////////////////////////
  26. uint32_t primes(uint max_number)
  27. {   vector<uint> primes = {2};
  28.  
  29.     for(uint i = 3; i < max_number; i += 2)
  30.     {   auto last = std::upper_bound(primes.begin(),
  31.                                      primes.end  (),
  32.                                      uint(sqrt(i)));
  33.         for(auto it  = primes.begin();
  34.                  it != last;
  35.                ++it )
  36.         {   if (i % (*it) == 0) goto next;
  37.         }
  38.         primes.push_back(i);
  39. next: ;
  40.     }
  41.     return primes.size();
  42. }
  43.  
  44. //////////////////////////////////////////////////////////////////////////////
  45. uint primes2(uint max_number)
  46. {   vector<uint> primes;
  47.  
  48.     for(uint i = 2; i <= max_number; i++)
  49.     {   auto max = uint(sqrt(i));
  50.  
  51.         for(auto &prime : primes)
  52.         {   if(prime     >   max) break;
  53.             if(i % prime ==    0) goto next;
  54.         }
  55.         primes.push_back(i);
  56. next: ;    
  57.     }
  58.     return primes.size();
  59. }
  60.  
  61. //////////////////////////////////////////////////////////////////////////////
  62. #define TIMER_START auto s = chrono::high_resolution_clock::now()
  63. #define TIMER_END   auto t = chrono::high_resolution_clock::now() - s;
  64. #define TIMER_LOG(v) cout << v << " "\
  65.                      << chrono::duration<double, milli>(t).count() << "\n"
  66.  
  67. const uint NUMBER = 5000000;
  68.  
  69. void test(uint (*fn)(uint))
  70. {   TIMER_START;
  71.         auto count = fn(NUMBER);
  72.     TIMER_END;
  73.  
  74.     TIMER_LOG(count);
  75. }
  76.  
  77. void test()
  78. {   TIMER_START;
  79.         Task  my(NUMBER);
  80.     TIMER_END;
  81.  
  82.     TIMER_LOG(my.result);
  83. }
  84.  
  85. //////////////////////////////////////////////////////////////////////////////
  86. int main()
  87. {   cout << "primes 1: ";
  88.     test(primes);
  89.  
  90.     cout << "primes 2: ";
  91.     test(primes2);
  92.  
  93.     cout << "my      : ";
  94.     test();
  95. }
  96.  
Success #stdin #stdout 2.2s 6864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
primes 1: 348513 477.905
primes 2: 348513 444.416
my      : 348513 1275.86
https://ideone.com/zy3P3y
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!