素数筛法
素数筛法
Eratosthenes 筛法
基本思想
一个数可以质因数分解为几个素数的乘积,那么一个素数的倍数一定是合数,且素数不会为素数的倍数。
代码
使用 book 数组记录 i 是否为素数
for(int i=1;i<=n;i++)
if(!book[i])
for(int j=1;i*j<=n;j++)
book[j]=1;
Euler 筛法
基本思想
已经筛过的数无需再筛,这是对上面筛法浪费的时间的优化。
代码
for(int i=2;i<=n;i++)
{
if(!book[i])
pri[++cnt]=i;
for(int j=1;j<=cnt;j++)
{
if((long long)pri[j]*(long long)i>n)
break;
book[i*pri[j]]=1;
if(!(i%pri[j]))
break;
}
}