GESP五级 质数筛

一、质数筛概述

• 用途：批量生成≤n的所有质数，效率远高于逐个判断质数
• 考点：埃拉托斯特尼筛法（埃氏筛）、欧拉筛（线性筛）的代码实现、优化原理、时间复杂度对比

二、埃拉托斯特尼筛法（埃氏筛）

1. 核心原理

从2开始，将每个质数的所有倍数标记为合数，最终未被标记的就是质数。

2. 模板代码

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true); // 先全部标记是质数
    is_prime[0] = is_prime[1] = false; // 0和1不是质数
    for (int i = 2; i <= n; i++) { // 从2开始标所有质数的倍数
        if (is_prime[i]) { // i是质数
            for (int j = i * i; j <= n; j += i) { // 标记i的倍数
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

3. 优化版（从i*i开始）

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）

只筛一次的核心逻辑

欧拉筛的关键在于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. 完整代码

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 线性筛（必考对比）

坑点

• ❌ 错误：线性筛一定比埃氏筛快
• ✅ 正确：n≤1e7时，埃氏筛实际速度通常优于线性筛

五、考点

• 埃氏筛从i*i开始的原因：小于i*i的i的倍数已被更小质因子筛过
• 线性筛的核心break条件：i % primes[j] == 0
• 线性筛内层循环必须同时满足：j < primes.size() 和 i * primes[j] <= n

• 批量生成素数表的最优选择：

  • n≤1e7：埃氏筛（实际更快）
  • n>1e7：线性筛（理论复杂度更优）
• 单个质数判断适合：少量数的质数检测；筛法适合：批量生成素数表