const long maxn=1000001;
bool prime[maxn];
//筛选法求素数
//0代表素数，1代表非素数
void primeinit(){
long long i=2,t;
for(i=4;i<maxn;i=i+2)
prime[i]=false;
for(i=3;i<maxn;i=i+2)
{
if(prime[i])
{
t=i*i;
while(t<maxn)
{
prime[t]=false;
t=t+i;//<<2;//偶数倍不用检测i*i为奇数，故i*i+2i必为奇数
}
}
}
}