vector<int>pr;
bool p[500000005];//this array consumes ~500MB of space. The Memory limit is 1024MB, so it's enough.
void primes(){
    for(int i=2;i<=n;i++){
        if(!p[i])pr.push_back(i);
        for(int j=0;j<pr.size() and pr[j]*i<=n;j++){
            p[pr[j]*i]=true;
            if(i%pr[j]==0){
                break;
            }
        }
    }
}