const int N=1e6+10;

vector<int> primes(N,1);
vector<int> p;

void get_primes(int n){
    for(int i=2;i<=n;i++)
    {
        if(primes[i]==1)
        {
            p.push_back(i);
            for(int j=i+i;j<=n;j+=i)
                primes[j]=0;
        }
    }
}