素数筛

快速求 n 以内的素数

埃氏筛 the Sieve of Eratosthenes

复杂度 O(nloglogn)O(n \log \log n)

筛的过程中,会重复筛到同一个数。比如 12 同时被 2 和 3 筛到。

线性筛

复杂度 O(n)O(n)

让每一个合数被其最小的质因数筛到,比如 12=3*4=6*2 需要被 6 划去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}
}
}

Ref

算法学习笔记(17): 素数筛 - 知乎 (zhihu.com)

作者

Ryen Xiang

发布于

2024-05-30

更新于

2024-08-05

许可协议


网络回响

评论