【算法基础篇】（三十九）数论之从质数判定到高效筛法：质数相关核心技能全解析-程序员充电站

前言

在算法竞赛的数论板块中，质数相关问题始终是高频考点。无论是判断单个数字是否为质数，还是快速筛选出一定范围内的所有质数，这些基础技能不仅是解决复杂数论问题的基石，更是拉开竞赛分数差距的关键。本文将从质数的定义出发，深入剖析质数判定的优化思路，详解埃氏筛法与线性筛法的原理与实现，带大家彻底掌握这部分核心内容。下面就让我们正式开始吧！

一、质数的定义与直观判定

1.1 质数与合数的概念

质数（又称素数）是指大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。与之相对的是合数，合数是指大于 1 且不是质数的自然数。特别规定：1 既不是质数也不是合数。

这个定义看似简单，但在实际判定时却藏着不少优化空间。比如判断一个数 x 是否为质数，最直观的思路是检查从 2 到 x-1 的所有整数是否能整除 x。但这样的暴力解法效率极低，当 x 达到 1e5 甚至更大时，必然会超时。

1.2 试除法的优化：从 O (n) 到 O (√n)

我们可以通过一个关键性质优化判定过程：如果 a 是 x 的约数，那么 x/a 也一定是 x 的约数。这意味着我们无需检查到 x-1，只需检查到√x 即可。因为如果 x 存在大于√x 的因数，那么它对应的另一个因数必然小于√x，在此之前就已经被检查过了。

举个例子，判断 100 是否为质数：√100=10，我们只需检查 2 到 10 之间的数。发现 2 能整除 100，直接判定 100 为合数，无需继续检查后续数字。

此外，在代码实现时，为了避免使用 sqrt 函数带来的精度问题，我们可以采用i <= x / i的写法，既保证了逻辑正确性，又提升了代码效率。

1.3 C++ 实现质数判定函数

bool isprime(int x) { if (x <= 1) return false; // 小于等于1的数直接排除 // 试除法核心：枚举到√x即可 for (int i = 2; i <= x / i; ++i) { if (x % i == 0) return false; // 存在其他因数，不是质数 } return true; // 未找到其他因数，是质数 }

这个函数的时间复杂度为O (√x)，对于 1e9 以内的单个数字判定完全足够。比如判断 1e9+7 是否为质数，只需循环约 3e4 次，效率极高。

1.4 实战例题：洛谷 P5736 质数筛

题目链接：https://www.luogu.com.cn/problem/P5736

题目描述：输入 n 个不大于 1e5 的正整数，去除掉不是质数的数字，依次输出剩余的质数。

解题思路：对于每个输入的数字，调用上述 isprime 函数进行判定，将判定为质数的数字输出即可。

C++ 参考代码：

#include <iostream> using namespace std; bool isprime(int x) { if (x <= 1) return false; for (int i = 2; i <= x / i; ++i) { if (x % i == 0) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; ++i) { int x; cin >> x; if (isprime(x)) { cout << x << " "; } } cout << endl; return 0; }

代码优化说明：使用ios::sync_with_stdio(false);和cin.tie(nullptr);关闭输入输出同步，提升大数据量下的读取速度，避免因输入输出耗时导致超时。

二、筛法入门：埃氏筛法（Eratosthenes Sieve）

2.1 筛法的核心思想

当需要找出 [1, n] 范围内的所有质数时，逐个判定的方法效率较低（时间复杂度 O (n√n)）。筛法的核心思想是 “标记非质数”：利用质数的倍数一定是合数的性质，从 2 开始，将每个质数的所有倍数标记为合数，未被标记的数即为质数。

2.2 埃氏筛法的基本实现

初始化一个布尔数组 st，st [i]表示数字 i 是否被标记为合数（初始值均为 false）。
从 2 开始遍历到 n：
如果 st [i] 为 false，说明 i 是质数，将其记录下来。
然后将 i 的所有倍数（从 ii 开始，而非 2i）标记为 true。这里从 ii 开始是因为小于 ii 的倍数已经被更小的质数标记过了（比如 i=5 时，52=10 已被 2 标记，53=15 已被 3 标记，只需从 5*5=25 开始标记）。

2.3 C++ 实现埃氏筛法

const int MAXN = 1e6 + 10; bool st[MAXN]; // 标记是否为合数 int primes[MAXN], cnt; // 存储质数，cnt为质数个数 void eratosthenes_sieve(int n) { memset(st, false, sizeof st); cnt = 0; for (int i = 2; i <= n; ++i) { if (!st[i]) { // i是质数 primes[++cnt] = i; // 从i*i开始标记倍数 for (long long j = 1LL * i * i; j <= n; j += i) { st[j] = true; } } } }

2.4 埃氏筛法的时间复杂度与优化

埃氏筛法的时间复杂度为O (n log log n)，这个复杂度非常接近线性，对于 n=1e6 的范围，几乎可以瞬间完成筛选。

关键优化点：

使用long long类型的 j 避免溢出：当 i 接近√n 时，ii 可能超过 int 的范围（比如 i=1e5 时，ii=1e10，超过 int 的最大值 2e9），因此需要用 1LL 强制转换为长整型。
数组初始化优化：使用memset函数快速初始化数组，效率大大高于循环赋值。

2.5 实战例题：洛谷 P3383 模板线性筛素数

题目链接：https://www.luogu.com.cn/problem/P3383

题目描述：给定范围 n 和 q 个询问，每次输出第 k 小的素数。

解题思路：先用埃氏筛法筛选出 [1, n] 范围内的所有质数，存储在 primes 数组中，然后直接响应每个询问。

C++ 参考代码：

#include <iostream> #include <cstring> using namespace std; const int MAXN = 1e8 + 10; // 根据题目n的范围调整 bool st[MAXN]; int primes[MAXN], cnt; void eratosthenes_sieve(int n) { memset(st, false, sizeof st); cnt = 0; for (int i = 2; i <= n; ++i) { if (!st[i]) { primes[++cnt] = i; for (long long j = 1LL * i * i; j <= n; j += i) { st[j] = true; } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; eratosthenes_sieve(n); while (q--) { int k; cin >> k; cout << primes[k] << endl; } return 0; }

注意事项：当 n 的范围较大（如 1e8）时，需要注意数组的内存占用。bool 类型数组每个元素占 1 字节，1e8+10 的数组约占 100MB，在竞赛允许的内存范围内。

三、筛法巅峰：线性筛法（欧拉筛法）

3.1 埃氏筛法的局限性

埃氏筛法虽然高效，但存在一个问题：某些合数会被多个质数重复标记。比如 12，会被 2 标记一次，又会被 3 标记一次。这虽然不影响最终结果，但造成了不必要的计算开销。

线性筛法（又称欧拉筛法）的核心创新点是：让每个合数只被其最小质因数标记一次，从而实现 O (n) 的线性时间复杂度，是竞赛中筛选质数的最优方法。

3.2 线性筛法的核心原理

同样使用 st 数组标记合数，primes 数组存储已找到的质数。
遍历每个数 i（从 2 到 n）：
如果 i 未被标记，说明 i 是质数，将其加入 primes 数组。
遍历 primes 数组中的每个质数p [j]：
计算ip [j]，如果ip [j] > n则跳出循环。
将i*p [j]标记为合数。
关键步骤：如果 i 能被 p [j] 整除，立即跳出循环。因为此时 p [j] 是 i 的最小质因数，也是 ip [j] 的最小质因数；如果继续遍历更大的质数，就会导致 ip [j] 被更大的质因数标记，违背 “只被最小质因数标记” 的原则。

3.3 线性筛法的逻辑拆解

我们以 i=6 为例，详细拆解线性筛法的执行过程：

primes 数组中已有 [2, 3, 5]。
遍历 p [j]=2：6*2=12，标记 12 为合数；由于 6%2==0，立即跳出循环。
这里 12 的最小质因数是 2，因此只被 2 标记一次，不会再被 3 标记（6*3=18，18 会在 i=9 时被 3 标记）。

再以 i=5（质数）为例：

遍历 p [j]=2：5*2=10，标记 10（最小质因数 2）。
p [j]=3：5*3=15，标记 15（最小质因数 3）。
p [j]=5：5*5=25，标记 25（最小质因数 5）。
p [j]=7：5*7=35>n（假设 n=30），跳出循环。

通过这种方式，每个合数都只被其最小质因数标记一次，确保了线性时间复杂度。

3.4 C++ 实现线性筛法

const int MAXN = 1e7 + 10; bool st[MAXN]; int primes[MAXN], cnt; void euler_sieve(int n) { memset(st, false, sizeof st); cnt = 0; for (int i = 2; i <= n; ++i) { if (!st[i]) { // i是质数 primes[++cnt] = i; } // 遍历所有已找到的质数，标记i*primes[j]为合数 for (int j = 1; 1LL * i * primes[j] <= n; ++j) { st[i * primes[j]] = true; if (i % primes[j] == 0) { // primes[j]是i的最小质因数 break; } } } }

3.5 线性筛法的优势与应用场景

线性筛法的时间复杂度严格为O (n)，在 n=1e7 的范围内，其速度远快于埃氏筛法。更重要的是，线性筛法在筛选质数的同时，还能方便地求出每个数的最小质因数，这为后续的质因数分解、欧拉函数计算等操作提供了极大便利。

四、进阶实战：质数相关经典例题解析

4.1 例题 1：洛谷 P1835 素数密度

题目链接：https://www.luogu.com.cn/problem/P1835

题目描述：给定 L 和 R，计算区间 [L, R] 中素数的个数（1≤L≤R<2^31，R-L≤1e6）。

难点分析：R 的范围最大为 2^31-1，直接筛选 [1, R] 范围内的质数会导致数组过大（需要 2^31 字节，约 2GB），内存无法承受。

解题思路：利用 “区间筛法”，核心思想是：

对于区间 [L, R] 中的数，其质因数一定不大于√R。因此先筛选出 [1, √R] 范围内的所有质数。
用这些质数去标记 [L, R] 范围内的倍数，未被标记的数即为质数。

C++ 参考代码：

#include <iostream> #include <cstring> #include <cmath> using namespace std; typedef long long LL; const int MAXN = 1e6 + 10; bool st_prime[MAXN]; // 标记[1, sqrt(R)]的质数 bool st_range[MAXN]; // 标记[L, R]的合数 int primes[MAXN], cnt; // 筛选[1, n]的质数 void sieve(LL n) { memset(st_prime, false, sizeof st_prime); cnt = 0; for (LL i = 2; i <= n; ++i) { if (!st_prime[i]) { primes[++cnt] = i; for (LL j = i * i; j <= n; j += i) { st_prime[j] = true; } } } } int count_primes(LL L, LL R) { memset(st_range, false, sizeof st_range); // 用[1, sqrt(R)]的质数标记[L, R]的倍数 for (int i = 1; i <= cnt; ++i) { LL p = primes[i]; // 计算区间[L, R]中p的最小倍数：max(p*2, ceil(L/p)*p) LL start = max(2LL * p, (L + p - 1) / p * p); for (LL j = start; j <= R; j += p) { st_range[j - L] = true; // 映射到数组索引 } } // 统计未被标记的数（质数） int res = 0; for (LL i = L; i <= R; ++i) { if (i < 2) continue; // 小于2的数不是质数 if (!st_range[i - L]) { ++res; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); LL L, R; cin >> L >> R; LL sqrt_R = sqrt(R); sieve(sqrt_R); cout << count_primes(L, R) << endl; return 0; }

代码解析：

由于 R-L≤1e6，st_range 数组只需开 1e6+10 的大小，内存占用仅 1MB 左右，完全可行。
计算 start 时，使用(L + p - 1) / p * p可以快速求出大于等于 L 的最小 p 的倍数，避免了浮点数运算。

4.2 例题 2：UVA543 Goldbach's Conjecture

题目链接：https://www.luogu.com.cn/problem/UVA543

题目描述：验证哥德巴赫猜想：任意一个大于 4 的偶数都可以拆成两个奇质数之和。对于每个输入的偶数 n，输出 b-a 最大的一组解（a≤b，a 和 b 均为奇质数）。

解题思路：

先用线性筛法筛选出 1e6 以内的所有质数（题目要求验证小于 1e6 的数）。
对于每个偶数 n，从最小的奇质数 3 开始遍历，检查 n-a 是否为奇质数。找到第一组满足条件的 (a, n-a) 即为 b-a 最大的解（因为 a 越小，b 越大，差值越大）。

C++ 参考代码：

#include <iostream> #include <cstring> using namespace std; const int MAXN = 1e6 + 10; bool st[MAXN]; int primes[MAXN], cnt; void euler_sieve(int n) { memset(st, false, sizeof st); cnt = 0; for (int i = 2; i <= n; ++i) { if (!st[i]) { primes[++cnt] = i; } for (int j = 1; 1LL * i * primes[j] <= n; ++j) { st[i * primes[j]] = true; if (i % primes[j] == 0) { break; } } } } void solve(int n) { // 从最小的奇质数开始查找 for (int i = 2; i <= cnt; ++i) { int a = primes[i]; int b = n - a; if (b < a) continue; // 保证a<=b if (!st[b]) { // b是质数 printf("%d = %d + %d\n", n, a, b); return; } } printf("Goldbach's conjecture is wrong.\n"); } int main() { euler_sieve(1e6); // 预处理1e6以内的质数 int n; while (cin >> n && n) { solve(n); } return 0; }

优化说明：预处理 1e6 以内的质数后，每个查询的时间复杂度为 O (π(√n))（π(x) 表示 x 以内的质数个数），效率极高，即使处理多组数据也能快速响应。

五、质数相关算法的常见误区与优化技巧

5.1 常见误区

整数溢出问题：在计算i*p [j]或p 的幂次时，容易超出 int 的范围，导致程序出错。解决方案是使用 long long 类型进行中间计算。
数组初始化错误：筛法中数组未初始化或初始化不完全，导致标记错误。建议使用 memset 函数进行初始化，注意 memset 按字节赋值，仅适用于 bool、char 数组或清零 int 数组。
边界条件处理不当：比如将 1 判定为质数、筛选时从 1 开始遍历、未处理 L=1 的情况等。需要严格遵循质数的定义，仔细处理边界。

5.2 优化技巧

内存优化：对于大范围筛选（如 1e8），可以使用 bitset 代替 bool 数组，将内存占用减少到原来的 1/8（bitset 中每个元素占 1 位）。
输入输出优化：竞赛中大数据量的输入输出会占用大量时间，建议使用ios::sync_with_stdio(false);cin.tie(nullptr);或用scanf/printf代替cin/cout。
预处理优化：对于多组查询的题目，提前预处理出最大范围的质数和相关信息（如质因子、欧拉函数等），避免重复计算。

总结

质数判定与筛法是算法竞赛数论部分的基础，掌握这些技能不仅能解决直接的质数相关问题，还能为后续学习质因数分解、欧拉函数、同余方程等复杂数论内容打下坚实基础。
在实际竞赛中，质数相关问题往往会与其他数论知识结合考查，比如与欧拉函数结合的 GCD 计数问题、与中国剩余定理结合的模运算问题等。因此，除了掌握本文介绍的内容，还需要不断拓展知识面，多做综合性题目，提升知识的融会贯通能力。
最后，建议大家多动手实现代码，通过调试理解算法的核心逻辑，同时关注题目中的数据范围，选择合适的算法和优化方式。只有通过大量练习，才能在竞赛中快速准确地解决质数相关问题，拿到关键分数。