Echo89

Prime Calculator (C++)

Feb 18th, 2015
202
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream> // cout
  2. #include <math.h> // sqrt
  3. #include <time.h> // clock/CLOCKS_PER_SEC
  4. #include <stdlib.h> // malloc/free
  5.  
  6. using namespace std;
  7.  
  8. int main(int argc, const char * argv[]) {
  9.     int n = 1000000000;
  10.     int i;
  11.     int j;
  12.     int k;
  13.     int s;
  14.     int c;
  15.     int sr;
  16.     int * a = (int*)malloc((size_t)n * sizeof(int));
  17.    
  18.     for(i = 0; i < n; i++) {
  19.         a[i] = 1;
  20.     }
  21.    
  22.     clock_t t = clock();
  23.    
  24.     sr = sqrt(n);
  25.     for(i = 2; i <= sr; i++) {
  26.         if(a[i]) {
  27.             s = i * i;
  28.             for(k = 0, j = 0; j <= n; j = s + (k * i), k++) {
  29.                 a[j] = 0;
  30.             }
  31.         }
  32.     }
  33.    
  34.     t = clock() - t;
  35.    
  36.     c = 0;
  37.     for(i = 2; i < n; i++) {
  38.         if(a[i]) {
  39.             //cout << i << " ";
  40.             c++;
  41.         }
  42.     }
  43.    
  44.     cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";
  45.    
  46.     free(a);
  47.    
  48.     return 0;
  49. }
RAW Paste Data