欧拉筛（模版）

//欧拉筛模版
const int maxn=1e6+7;
int vis[maxn];
int prime[maxn]; //最后prime数组里面储存的是所有的素数，从小到大排列
void init()
{
    int cnt=0;
    vis[0]=vis[1]=1; //1代表不是素数，0代表是素数
    for(int i=2;i<=1e5;i++)
    {
        if(vis[i]==0) prime[cnt++]=i;
        for(int j=0; j<cnt && i*prime[j]<=maxn ; j++)
        {
            vis[i*prime[j]]=1;             //欧拉筛模板
            if(i%prime[j]==0) break;
        }
    }
}