Advertisement
NAbdulla

prime generation with Sieve

Jun 17th, 2015
225
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <bitset>
  4.  
  5. using namespace std;
  6.  
  7. #define MAX 2147483647LL
  8.  
  9. bitset<(MAX+5)>sieve;
  10.  
  11. void filter()
  12. {
  13.     int i, j, s = sqrt(MAX);
  14.     sieve[0] = 1;
  15.     sieve[1] = 1;
  16.     for(i = 4; i <= MAX; i += 2)sieve[i] = true;
  17.     for(i = 3; i <= s; i += 2){
  18.         if(!sieve[i]){
  19.             for(j = i*i; j <= MAX; j += (i+i))sieve[j] = true;
  20.         }
  21.     }
  22. }
  23.  
  24. int main()
  25. {
  26.     filter();
  27.     cout << "Number of primes from 2 to 2^31: " << MAX-sieve.count() << endl;
  28.     return 0;
  29. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement