const int Max=1e5;
int vis[Max],prime[Max];
void Prime()
{
    memset(vis,0,sizeof(vis));
    memset(prime,0,sizoef(prime));
    for(int i=2;i<Max;i++)
    {
        if(!vis[i]) prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]*i<Max;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
            //i%prime[j]==0的时候,后面的prime[m]*i就等于prime[i]*k*prime[m],欧拉筛核心是筛掉最小质因数,所以break
        }
    }
}