素数筛
欧拉筛
求小于(n)的所有正整数中的素数集合
(code :)
for(ll i=2;i<=n;++i)
{
if(!tag[i]) pri[++tot]=i;
for(ll j=1;j<=tot;++j)
{
ll k=i*pri[j];
if(k>n) break;
tag[k]=true;
if(i%pri[j]==0) break;
}
}
每个数只会被最小的素因子筛一次