fork download
copy 
  1. #include <vector>
  2. #include <cmath>
  3. #include <cstring>
  4.  
  5. int countPrimes_vector(int n) {  
  6.     int res = 0; 
  7.     std::vector<bool> bitmap(n, true);
  8.     for (int i = 2; i<n; ++i){
  9.         if(bitmap[i])
  10.           ++res;
  11.         if(sqrt(n)>i)
  12.         {
  13.              for(int j = i*i; j < n; j += i) bitmap[j] = false;
  14.         }
  15.     }
  16.     return res;
  17. }
  18.  
  19. int countPrimes_carray(int n) {  
  20.     int res = 0; 
  21.     bool* bitmap = new bool[n];
  22.     memset(bitmap, true, sizeof(bool) * n);
  23.     for (int i = 2; i<n; ++i){
  24.  
  25.         if(bitmap[i])++res;
  26.         if(sqrt(n)>i)
  27.         {
  28.              for(int j = i*i; j < n; j += i) bitmap[j] = false;
  29.         }
  30.     }
  31.     delete []bitmap;
  32.     return res;
  33. }
  34.  
  35. #include <chrono>
  36. #include <iostream>
  37.  
  38. using namespace std;
  39.  
  40. void test(const char* description, int (*fn)(int))
  41. {
  42.     using clock = std::chrono::steady_clock;
  43.     using ms = std::chrono::milliseconds;
  44.  
  45.     auto start = clock::now();
  46.  
  47.     int a;
  48.     for(int i=0; i<9; ++i)
  49.         a = countPrimes_vector(8000000); 
  50.  
  51.     auto end = clock::now();
  52.     auto diff = std::chrono::duration_cast<ms>(end - start);
  53.  
  54.     std::cout << "time for " << description << " = " << diff.count() << "ms\n";
  55. }
  56.  
  57. int main()
  58. {
  59.     test("carray", countPrimes_carray);
  60.     test("vector", countPrimes_vector);
  61. }
  62.  
Success #stdin #stdout 4.49s 3140KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
time for carray = 2251ms
time for vector = 2254ms
https://ideone.com/0Y9gQx
language:
C++14 (gcc 8.3)
created:
9 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!