<!--markdown--># GESP五级 质数筛
一、质数筛概述
- 用途：批量生成≤n的所有质数，效率远高于逐个判断质数
- 考点：埃拉托斯特尼筛法（埃氏筛）、欧拉筛（线性筛）的代码实现、优化原理、时间复杂度对比
---
二、埃拉托斯特尼筛法（埃氏筛）
1. 核心原理
从2开始，将每个质数的所有倍数标记为合数，最终未被标记的就是质数。
2. 模板代码
c++bool is_prime[MAXN]; // MAXN:题目要判断的最大数字
void prime() {
for(int i = 0; i < MAXN; i++) is_prime[i] = 1; // 先全部标记为是质数
is_prime[0] = is_prime[1] = 0; // 0和1不是质数
for (int i = 2; i <= n; i++) { // 从2开始标所有质数的倍数
if (is_prime[i] == 1) { // i是质数
for (int j = i * i; j <= n; j += i) { // 遍历i的倍数
is_prime[j] = 0; // 标记i的倍数为非质数
}
}
}
}
3. 优化版（从i*i开始）
c++for (long long j = (long long)i * i; j <= n; j += i) {
is_prime[j] = false;
}
int j = i * i->long long j = (long long)i * i- 优化原因：小于i*i的i的倍数，已经被更小的质因子筛过了（真题第4题考点）
- 例：i=5时，10、15、20已经被2、3筛过，只需从25开始
4. 时间复杂度
O(n log log n)，接近线性，实际运行效率极高
---
三、欧拉筛（线性筛）
埃氏筛对例如90，会用2、3、5重复筛除，还可以优化。
1. 核心原理
每个合数只会被它的最小质因子筛掉一次，彻底避免重复标记，实现真正的线性时间复杂度。
欧拉筛（线性筛）简化示例表（n=30）
| i | 质数表 primes | 筛除的数 (i×p) | 核心逻辑（只筛一次的关键） |
|---|---|---|---|
| 2 | [2] | 4 | 2是质数，筛 2×2；2%2=0 → break |
| 3 | [2,3] | 6、9 | 3是质数，筛3×2/3×3；3%3=0 → break |
| 4 | [2,3] | 8 | 仅筛4×2（最小质因子）；4%2=0 → break，不筛4×3=12 |
| 5 | [2,3,5] | 10、15、25 | 5是质数，连续筛；5%5=0 → break |
| 6 | [2,3,5] | 12 | 仅筛6×2；6%2=0 → break，不筛6×3=18 |
| 7 | [2,3,5,7] | 14、21 | 7是质数，筛7×2/7×3；7×5=35>30 → 越界break |
| 8 | [2,3,5,7] | 16 | 仅筛8×2；8%2=0 → break，不筛8×3=24 |
---
只筛一次的核心逻辑
欧拉筛的关键在于if (i % p == 0) break：
- 当
p能整除i时，i可以写成p × k（p是i的最小质因子），此时i × p'（p' > p）的最小质因子一定是p，后续会在i' = k × p'时由p筛除，因此直接break，避免重复筛除。
比如：
i = 4时：12不会被4×3筛除，因为4是2的倍数，4的倍数也一定是2的倍数，后续总能被2给筛除，所以判断4%2==0后break了。- 同理，
18不会被6×3筛除（i=6时break），6 * 2筛掉12后，发现6是2的倍数，则后续6的倍数都可以由2在某个时间筛除，即由9×2筛除（2是18的最小质因子）。
2. 完整代码
c++vector<int> euler_sieve(int n) {
vector<bool> is_composite(n + 1, false);
vector<int> primes; // 存储所有质数
for (int i = 2; i <= n; i++) {
if (!is_composite[i]) {
primes.push_back(i); // 未被标记，是质数
}
// 内层循环条件：遍历当前素数表 & 标记的数在需求范围内
for (int j = 0; j < primes.size() && (long long)i * primes[j] <= n; j++) {
is_composite[i * primes[j]] = true; // 标记乘积为合数
// 核心优化语句，一旦发现i是当前质数的因数，则break
if (i % primes[j] == 0) {
break;
}
}
}
return primes;
}
3. 时间复杂度
O(n)，理论上最优的质数筛法
---
四、埃氏筛 vs 线性筛（必考对比）
| 特性 | 埃氏筛 | 线性筛（欧拉筛） |
|---|---|---|
| 核心思想 | 标记所有质数的倍数 | 每个合数仅被最小质因子标记一次 |
| 时间复杂度 | O(n log log n) | O(n) |
| 重复标记 | 会（如12被2、3各标记一次） | 不会 |
| 小规模数据实际速度（n≤1e7） | 更快（实现简单，常数小） | 稍慢（逻辑复杂，常数大） |
| 代码复杂度 | 简单 | 中等 |
坑点
- ❌ 错误：线性筛一定比埃氏筛快
- ✅ 正确：n≤1e7时，埃氏筛实际速度通常优于线性筛
---
五、考点
| 说法 | 对错 | 说明 |
|---|---|---|
| 线性筛时间复杂度更低，所有情况都应优先使用 | ❌ | n≤1e7时埃氏筛实际更快 |
| 线性筛每个合数只会被最小质因子筛去一次 | ✅ | 线性筛的核心原理 |
| 线性筛时间复杂度为O(n) | ✅ | 无重复标记，线性时间 |
| 线性筛通过"每个合数被最大质因子筛去"实现O(n) | ❌ | 是最小质因子，不是最大 |
| 埃氏筛会对同一个合数进行多次标记 | ✅ | 如12被2、3各标记一次 |
| 单个质数判断比筛法效率更高 | ❌ | 批量生成素数表时，筛法效率远高于逐个判断 |
- 埃氏筛从
i*i开始的原因：小于i*i的i的倍数已被更小质因子筛过 - 线性筛的核心break条件：
i % primes[j] == 0 - 线性筛内层循环必须同时满足：
j < primes.size()和i * primes[j] <= n - 批量生成素数表的最优选择：
- n≤1e7：埃氏筛（实际更快）
- n>1e7：线性筛（理论复杂度更优）
- 单个质数判断适合：少量数的质数检测；筛法适合：批量生成素数表