素数筛
埃氏筛 the Sieve of_Eratosthenes#
复杂度 O(n \log \log n)
筛的过程中，会重复筛到同一个数。比如 12 同时被 2 和 3 筛到。
线性筛#
复杂度 O(n)
让每一个合数被其最小的质因数筛到，比如 12=3*4=6*2 需要被 6 划去。
cpp
bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n)
{
for (int i = 2; i <= n; i++)
{
if (!isnp[i])
primes.push_back(i);
for (int p : primes)
{
if (p * i > n)
break;
isnp[p * i] = 1;
if (i % p == 0) //保证每个数最多被筛一次。
break;
}
}
}
算法学习笔记(17): 素数筛 - 知乎 (zhihu.com)
最后更新: 2022-11-15