6 质数查找与筛法

GESP C++ 五级：质数查找与筛法

核心目标：掌握质数的定义与试除法判定，熟练编写埃氏筛与线性筛代码，理解两种筛法的复杂度差异与原理，掌握用线性筛预处理最小质因子（SPF）实现 O(log n) 质因数分解的技巧，能辨析筛法相关选择题。
试除法判单个数 O(√n)，6k±1 优化后约快 3 倍；埃氏筛 O(n log log n)，从 i×i 开始标记减少重复；线性筛 O(n)，每个合数只被其最小质因子筛一次；预处理 SPF 后，分解任意数只需 O(log n)。

一、考纲定位

根据 CCF 官方考纲，五级知识点明确要求：“掌握辗转相除法、素数表的埃氏筛法和线性筛法、唯一分解定理的原理和应用”，考核目标进一步要求“能够使用辗转相除法、素数表的埃氏筛法和线性筛法、唯一分解定理等相关知识解决相应的问题”。

在 GESP 五级中，质数与筛法是数论模块的高频考点，常见考法：

考法	说明	典型题目
质数判定代码辨析	判断试除法代码的正确性	2025年6月第5题、第7题
埃氏筛代码填空	补全标记合数的循环	2025年6月选择题
线性筛代码填空	补全 `if (i % p == 0) break;`	2026年3月选择题
筛法复杂度判断	埃氏筛 vs 线性筛	判断题、选择题
筛法综合应用	用筛法解决互质数选取等问题	数字选取

二、质数的定义与试除法判定

2.1 质数的定义

质数（素数）是大于 1 的自然数中，除了 1 和它本身外，不能被其他自然数整除的数。2 是最小的质数，也是唯一的偶质数。

2.2 朴素试除法

最直观的判定方法：检查 2 到 n-1 之间是否有能整除 n 的数。

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

2.3 优化一：枚举到 √n

核心原理：若 n 是合数，则 n = a × b，其中必有 a ≤ √n 或 b ≤ √n。因此只需检查 2 到 √n 即可。

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {   // 等价于 i <= sqrt(n)
        if (n % i == 0) return false;
    }
    return true;
}

复杂度：O(√n)。当 n = 10⁹ 时，√n ≈ 31623，最多迭代约 3 万次。

2.4 优化二：6k±1 轮转筛法

数学原理：所有大于 3 的质数都可以表示为 6k±1 的形式（即 6k+1 或 6k-1）。因为：

6k+0 → 能被 6 整除 → 不是质数
6k+2 → 能被 2 整除 → 不是质数
6k+3 → 能被 3 整除 → 不是质数
6k+4 → 能被 2 整除 → 不是质数
6k+1 → 不能被 2 或 3 整除 → 可能是质数
6k+5（即 6k-1）→ 不能被 2 或 3 整除 → 可能是质数

因此，只需检查 2、3 以及形如 6k±1 的数，可减少约 2/3 的检查次数。

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    // 从 5 开始，检查 6k±1
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

复杂度：仍为 O(√n)，但常数因子约为原来的 1/3，实际运行约快 3 倍。

真题辨析（2025年6月第5题） ：关于判断正整数是否为质数的代码，说法正确的是？

C) 当前 while 循环正确的前提是：所有大于 3 的质数都符合 6k±1 形式
答案：C

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

3.1 核心思想

埃氏筛的思路是“反过来”：不去一个个判断，而是一口气把合数“划掉”，剩下的就是素数。从 2 开始从小到大扫描，每遇到一个质数 i，就把它的所有倍数标记为合数。

为什么这样正确：任何合数都有比它小的质因子。当扫描到某个数时它还未被标记，说明它没有比它小的质因子，因此它一定是质数。

3.2 标准代码

const int N = 1000005;
bool is_prime[N];   // 默认false，false表示未筛去

void eratosthenes(int n) {
    fill(is_prime, is_prime + n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {       // 外层到 √n
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {   // 内层从 i*i 开始
                is_prime[j] = false;
            }
        }
    }
}

3.3 两个关键优化

优化一：内层从 i*i 开始，而不是 2*i

为什么从 i*i 开始？因为 i 的更小倍数（如 2*i、3*i、…、(i-1)*i）已经被更小的质数（2、3、…、i-1）标记过了。例如，当 i=3 时，2×3=6 已经在 i=2 时被标记；3×3=9 是第一个没有被之前质数标记的倍数。因此直接从 i*i 开始，可以显著减少重复标记。

优化二：外层到 √n 即可

大于 √n 的质数，其倍数 i*i 已经超过 n，内层循环不会执行。因此外层只需枚举到 √n。

3.4 复杂度

埃氏筛的时间复杂度为 O(n log log n)。由调和级数的求和性质决定：标记次数约为 n/2 + n/3 + n/5 + … = n × (1/2 + 1/3 + 1/5 + …) ≈ n log log n。

四、线性筛（欧拉筛）

4.1 核心思想

线性筛，又称欧拉筛。每个合数只被它的最小质因子筛去一次，因此时间复杂度为 O(n)。

4.2 标准代码

const int N = 1000005;
vector<int> primes;
bool is_composite[N];

void linear_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) primes.push_back(i);   // i 是质数
        for (int p : primes) {
            if (p * i > n) break;                    // 超出范围
            is_composite[p * i] = true;
            if (i % p == 0) break;                   // 关键：保证 p 是 p*i 的最小质因子
        }
    }
}

4.3 关键语句 `if (i % p == 0) break;` 的作用

当 p 整除 i 时，p 是 i 的最小质因子，那么 p * i 的最小质因子也是 p。如果继续用更大的质数 p' 去乘 i，p' * i 的最小质因子仍然是 p（因为 p | i），但会被 p' 筛一次，造成重复标记。

举例：当 i=4，primes=[2,3] 时：

p=2：标记 8（8 的最小质因子是 2），因为 4%2==0，break。
如果不 break，继续 p=3，标记 12（12 的最小质因子是 2，不是 3）。但 12 应该被 i=6, p=2 时标记（6×2=12）。这就造成了重复标记。

因此 break 确保每个合数只被其最小质因子筛一次，这是 O(n) 复杂度的根本保证。

4.4 复杂度

线性筛的时间复杂度为 O(n)，空间复杂度 O(n)。每个合数有且仅有一次被其最小的质因数标记，从而避免重复操作，达到线性复杂度。

五、埃氏筛 vs 线性筛对比

对比项	埃氏筛	线性筛
时间复杂度	O(n log log n)	O(n)
空间复杂度	O(n)
核心操作	标记质数的所有倍数	质数 × 数生成合数
重复标记	有（同一个合数可能被多个质数标记）	无（只被最小质因子标记）
关键代码	`for (j = i*i; j <= n; j += i)`	`if (i % p == 0) break;`
代码复杂度	简单	稍复杂
适用场景	n ≤ 10⁷，简单够用	n 较大，追求极致效率

真题辨析（2025年6月第7题） ：关于判断整数是否为质数的代码，错误的说法是？

D) 埃氏筛算法比该代码及线性筛算法效率都高
答案：D。线性筛 O(n) 优于埃氏筛 O(n log log n)，埃氏筛优于朴素试除 O(n√n)，因此“埃氏筛比线性筛效率都高”是错误的。

六、线性筛预处理 SPF 与 O(log n) 分解

6.1 SPF 的定义

SPF（Smallest Prime Factor）即最小质因子。用线性筛预处理出每个数的最小质因子后，可以在 O(log n) 时间内完成任意一个不超过 n 的整数的质因数分解。

6.2 带 SPF 的线性筛

const int N = 1000005;
int spf[N];          // spf[i] = i 的最小质因子
vector<int> primes;

void sieve_spf(int n) {
    for (int i = 2; i <= n; i++) {
        if (spf[i] == 0) {        // i 是质数
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || p * i > n) break;
            spf[p * i] = p;       // p 是 p*i 的最小质因子
        }
    }
}

6.3 用 SPF 快速分解

void factorize_fast(int n) {
    while (n > 1) {
        int p = spf[n];
        int cnt = 0;
        while (n % p == 0) {
            n /= p;
            cnt++;
        }
        cout << p << "^" << cnt << endl;
    }
}

执行过程：每次取出当前 n 的最小质因子 spf[n]，反复除尽，然后 n 缩小，继续取新的 spf[n]。由于每次至少除以 2，循环次数不超过 log₂n。

6.4 两种分解方式对比

分解方式	预处理	单次分解复杂度	适用场景
试除法	无	O(√n)	单次分解、n ≤ 10⁹
SPF 预处理	O(n) 线性筛	O(log n)	多次分解、n 范围有限

七、GESP 五级真题精讲

真题1：数字选取（2025年9月）

题目：从 1~n 中选取尽可能多的整数，使得任意两个不同的整数均互质。求最大选取个数。

思路：数字 1 与任何数互质，选上。对于每个质数，它的所有倍数都不可选，所以最多只能选一个质数。答案 = 质数个数 + 1。

#include <bits/stdc++.h>
using namespace std;

int vis[100005], cnt;

int main() {
    int n;
    cin >> n;
    if (n == 1) { cout << 1; return 0; }
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            cnt++;
            for (int j = i + i; j <= n; j += i) vis[j] = 1;
        }
    }
    cout << cnt + 1;
    return 0;
}

核心考点：埃氏筛统计质数个数 + 互质数选取的策略分析。

真题2：因数分解（2023年9月）

题目：给定 n，输出质因数分解式。指数为1时不输出 ^1，乘号用 *。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool first = true;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { n /= i; cnt++; }
            if (!first) cout << " * ";
            first = false;
            if (cnt == 1) cout << i;
            else cout << i << "^" << cnt;
        }
    }
    if (n > 1) {
        if (!first) cout << " * ";
        cout << n;
    }
    cout << endl;
    return 0;
}

真题3：唯一分解定理与筛法关系（2026年3月判断题）

唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。
答案：√（正确）

解析：该命题是素数判定中基于试除法的核心原理。唯一分解定理本身说的是“每个大于 1 的整数都可以唯一地分解为质数的乘积”，它保证了分解的存在性与唯一性，并未直接给出“如何判断一个数是否为质数”。但题目逻辑成立，且是数论中判断质数的经典方法，故判为正确。

注意区分：“唯一分解定理是埃氏筛 O(n log log n) 的根本原因”这一说法是错误的。埃氏筛的复杂度由调和级数决定，与唯一分解定理没有直接关系。

八、易错点汇总

试除法忘记特判 n<2：1 和 0 都不是质数，必须单独处理。
试除法循环条件写错：i * i <= n，不是 i <= n。
6k±1 优化中步长错误：步长是 6，检查 i 和 i+2，不是 i 和 i+1。
埃氏筛内层从 2*i 开始：应从 i*i 开始，更小倍数已被标记。
埃氏筛外层枚举到 n：枚举到 √n 即可，大于 √n 的质数倍数已超出范围。
线性筛忘记 if (i % p == 0) break;：这是保证 O(n) 的关键，丢了会退化为近似埃氏筛。
线性筛 break 位置错误：is_composite[p*i] = true; 必须在 if (i % p == 0) break; 之前。
SPF 数组初始为 0：spf[i] == 0 表示 i 未被标记，即质数。
SPF 线性筛中 p > spf[i] 的判断：确保 p 是 p*i 的最小质因子。
混淆埃氏筛与线性筛复杂度：埃氏筛 O(n log log n)，线性筛 O(n)，线性筛更优。
“埃氏筛比线性筛效率高”是错误的：真题高频错误选项。
“唯一分解定理是埃氏筛复杂度的根本原因”是错误的：埃氏筛复杂度由调和级数决定。

九、速查表

需求	写法	关键注意
朴素试除	`for(i=2;i<n;i++) if(n%i==0) return false;`	O(n)
优化试除	`for(i=2;i*i<=n;i++) if(n%i==0) return false;`	O(√n)
6k±1 试除	`for(i=5;i*i<=n;i+=6) if(n%i==0
埃氏筛	`for(i=2;ii<=n;i++) if(is_prime[i]) for(j=ii;j<=n;j+=i) is_prime[j]=false;`	从 i*i 开始
埃氏筛复杂度	O(n log log n)	由调和级数决定
线性筛	`for(i=2;i<=n;i++){ if(!vis[i]) primes.push_back(i); for(p:primes){ if(pi>n)break; vis[pi]=true; if(i%p==0)break; } }`	break 不能丢
线性筛复杂度	O(n)	每个合数只筛一次
SPF 预处理	线性筛中记录 `spf[p*i] = p`	p 是 p*i 的最小质因子
SPF 分解	`while(n>1){ p=spf[n]; while(n%p==0) n/=p; }`	O(log n)
试除法分解	`for(i=2;i*i<=n;i++) if(n%i==0){ while(n%i==0)n/=i; }`	O(√n)
关系辨析	线性筛“最小质因子唯一”依赖唯一分解定理；埃氏筛复杂度与唯一分解定理无关	高频错误选项

十、总结

质数查找与筛法是 GESP 五级数论模块的核心内容。

质数判定用试除法，优化后枚举到 √n，复杂度 O(√n)。
6k±1 优化可减少约 2/3 的检查次数，实际运行约快 3 倍。
埃氏筛 O(n log log n)，从 i*i 开始标记，减少重复。
线性筛 O(n)，每个合数只被其最小质因子筛一次。
线性筛中 if (i % p == 0) break; 是保证 O(n) 的关键，不能丢。
线性筛“最小质因子唯一”这一性质的理论依据正是唯一分解定理。
埃氏筛的复杂度由调和级数决定，与唯一分解定理无直接关系。
预处理 SPF 后，质因数分解从 O(√n) 降为 O(log n)。
试除法适合单次分解大数；SPF 预处理适合多次分解或 n 范围有限。
多练“试除法代码辨析”“埃氏筛/线性筛代码填空”“复杂度对比”“SPF 分解”四类题。

复习建议：先把试除法（含 6k±1 优化）、埃氏筛、线性筛的标准代码写熟，确保闭卷能默写；再重点理解线性筛 break 的作用和 SPF 的更新逻辑；然后练习“数字选取”类筛法综合应用题；最后攻克“唯一分解定理与筛法关系”类辨析题，重点区分“哪些说法正确、哪些是张冠李戴”。考试中先判断题目考的是判定、筛法实现、复杂度还是综合应用，再套用对应知识作答。