Erathosieve

#define MX (1<<27)
#define IS(A) ((cn[A>>6]>>(A&63))&1)
#define ST(A) (cn[A>>6]|=1ULL<<((A&63)))
ll P[MX>>1]={2},L(1),cn[1+(MX>>6)];
void gen(){
    ST(0),ST(1);
    int Q(1+sqrt(MX));
//    for(ll i(4);i<MX;i+=2)ST(i);
    for(int k(3);k<=Q;k+=2)if(!IS(k))
        for(ll h(k<<1),j(k*k);j<MX;j+=h)ST(j);
    for(int i(3);i<MX;i+=2)if(!IS(i))P[L++]=i;
}