Bitwise Sieve.cpp

/* Bitwise Sieve */
/* Source : Shafayet's Planet */

#include <bits/stdc++.h>

using namespace std;

#define MAXN 3000008
int prime[MAXN/32];

bool check(int n, int pos)
{
    return (1<<pos) & n;
}

int sets(int n, int pos)
{
    return n = n | (1<<pos);
}

void sieve()
{
    int sqrtn = sqrt(MAXN);
    prime[1/32] = sets(prime[1/32], 1%32); // prime[1] = false;
    for(int i=2; i<=sqrtn; i++){
        if(check(prime[i/32], i%32) == 0){
            for(int j=i*i; j<MAXN; j+=i){
                prime[j/32] = sets(prime[j/32], j%32);
            }
        }
    }
}

int main()
{
    sieve();
    for(int i=1; i<100; i++){
        if(check(prime[i/32], i%32) == 0){
            cout << i << endl;
        }
    }
}