获取质数（素数）
封面图：孪生素数问题1
在竞赛和实际应用中，我们有时需要获取某个范围内的全部质数，通常有以下方法可供选择.
逐个计算法
我们知道一个数字的最大因子是他的算数平方根，只需要检查到floor(pow(i, 0.5)).
1
2
3
4
5
6
7
8
9
10
11
for (int i = 2; i <= 100; i++) {
int fact = 0;
int check = floor(pow(i, 0.5));
for (int j = 2; j <= check; j++) {
if (i % j == 0) {
fact = 1;
break;
}
}
if (!fact) printf("%d ", i);
}
很显然，这种方法并不好，我们的时间复杂度来到了$O(N \sqrt{N})$，显然可以通过跳过偶数等其他奇技淫巧优化，然而时间复杂度的量级不会变.
埃氏筛
埃氏筛是一种高效的在数盘里筛掉合数的方法，我们关注剩下来的数字就全都是质数.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isPrime[101];
for (int i = 0; i <= 100; i++) isPrime[i] = true;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= 100; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= 100; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 2; i <= 100; i++) {
if (isPrime[i]) printf("%d ", i);
}
这种方法是更优的，可以证明其时间复杂度为$O(N\log \log N)$.
其原理为遍历i从2到100，令j为i的倍数，我们逐个从数表中划去他们，因为他们含有因子i是合数，最后剩下的就是质数了.
思考：为什么从j = i*i开始计算合数？
其实这是一个优化过后的点，我们其实完全可以从2*i开始计算，但是这样会重复地筛去数字，例如
- 2 * 5 = 10 会被2筛去
- 3 * 5 = 15 会被3筛去
- 4 * 5 = 20 会被4筛去
- 5 * 5 = 25 尚未被筛去
因此我们选择从i的平方开始筛去数字，不然时间复杂度会比这大，退化为$O(N\log N)$.
更好的线性筛（欧拉筛）
优化到无重复
线性筛是埃氏筛的升级版本，我们可以在埃氏筛基础上优化算法. 具体来说，在埃氏筛算法中，有一些合数被我们划去了多次，导致了计算的浪费，比如
- 2 * 6 = 12
- 3 * 4 = 12
因此我们需要找到一种方法来唯一表示合数，并规定只有这个数字的 最小质因数 才有资格筛去这个数字，因此我们的代码做如下更改.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int primes[100];
bool isComposite[101] = {false};
int count = 0;
for (int i = 2; i <= 100; i++) {
if (!isComposite[i]) {
primes[count++] = i;
}
for (int j = 0; j < count && i * primes[j] <= 100; j++) {
isComposite[i * primes[j]] = true;
if (i % primes[j] == 0) break; // important
}
}
for (int i = 0; i < count; i++) {
printf("%d ", primes[i]);
}
如果一个数字i在之前的循环没有被筛去，说明i不含有小于i的因子，因此i的因子只有1与它本身，是质数，所以可以直接加入质数数组primes中.
最小质因数的证明
这里的核心在第11行，第11行的break跳出保证了我们的规则成立，具体证明如下，我们还是以12为例.
我们定义
\[M = i * p\]其中M是被筛掉的数字，i是从2到100的变量，p是primes[j]，是一个已知是素数的数字. 我们把i写左侧，p写右侧，合数M会由最小质因数p筛去.
- 6 * 2 = 12 合法，被2筛去
- 4 * 3 = 12 不合法，被3筛去，但是12的最小质因子是2
我们注意到，从小到大遍历primes的时候，第11行其实是在检查i是否包含因子p.
我们知道，合数一定由若干质数的乘积组成当i % primes[j]不为0时，我们知道i不含有质因子primes[j].
又因为primes[j]是从小到大遍历的，i不含有小于p的质因子，那整体数字M的最小质因子一定是p，我们可以使用p筛去M，这种情况持续到i % primes[j]为0.
此时如果我们继续使用primes[j+1,j+2...]筛去数字，会发现，数字M可以分解为
我们知道M有一个最小的质因子p，然而其被质数p’消去，显然违反了我们指定的规则，会导致重复，故我们应该在i % primes[j]为0的时候跳出循环.
这样，我们成功把时间复杂度降到了$O(N)$.
总结规律
通过特定的规则我们可以发现，只要能找到每个合数的唯一表示，并且通过得当的方法遍历它们，我们就能做到让筛无重复.
另一种线性筛
当然，线性筛不止这一种写法，这里引用一个B站视频供读者探索线性筛的变种2.
我们定义另一种唯一确定数字M的方法
其中
- p = lp(M)
- k ≥ 1
- p = q or p < lp(q)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int n = 100;
bool is_prime[101];
for (int i = 2; i <= n; i++) is_prime[i] = true;
int p = 2;
while (p * p <= n) {
int q = p;
while (p * q <= n) {
int x = p * q;
while (x <= n) {
is_prime[x] = false;
x = p * x;
}
q = q + 1;
while (q <= n && is_prime[q] == false) {
q = q + 1;
}
}
p = p + 1;
while (p <= n && is_prime[p] == false) {
p = p + 1;
}
}
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
printf("%d ", i);
}
}
B站真理元素,孪生素数问题 [EB/OL]. [2026-06-23]. https://www.bilibili.com/video/BV1Td7M6UE2b/ ↩
B站对数向往自由,从最小质因子到另一种线性筛 [EB/OL]. [2026-07-26]. https://www.bilibili.com/video/BV1JZ3762EUm/ ↩