#define nmax 10000005
bool NT[nmax];
void sang()
{
    memset(NT, true, nmax);
    NT[0]=NT[1]=false;
    for (int i=2; i<=sqrt(nmax); i++)
        if (NT[i])
            for (int j=i*i; j<=nmax; j+=i)
                NT[j]=false;
}