Skip to content

Instantly share code, notes, and snippets.

@PanagiotisPtr
Created April 21, 2017 16:25
Show Gist options
  • Save PanagiotisPtr/342115a2a69fd591799c27c9cae673d8 to your computer and use it in GitHub Desktop.
Save PanagiotisPtr/342115a2a69fd591799c27c9cae673d8 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes implementation with Bitset in C++
#include <iostream>
#include <bitset>
#include <cmath>
using namespace std;
int main(){
const int sieve_size = 1024;
bitset<sieve_size> sieve;
sieve.flip();
int finalBit = sqrt(sieve.size()) + 1;
// Perform sieve of Eratosthenes
for(int i = 2; i < finalBit; ++i){
if(sieve.test(i))
for(int j = 2*i; j < sieve_size; j+=i)sieve.reset(j);
}
// Print First prime numbers in range [2, 1023]
for(int i = 2; i < sieve_size; i++)
if(sieve.test(i))cout << i << " ";
cout << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment