蓝桥杯省赛 · 电子学会C/C++考级 · 全国青少年信息素养大赛：线性筛质数与质因数分解精讲-育师

本文面向准备蓝桥杯省赛、中国电子学会青少年软件编程（C/C++、Python）等级考试、全国青少年信息素养大赛算法挑战赛项的同学，拆解一个被三大赛事共同高频考察、却最容易被忽视的基础模块：质数筛法（埃氏筛 / 线性筛）与质因数分解。附原创练习题与 C++ / Python 双语言满分写法。

一、为什么这篇值得刷

翻看近年的蓝桥杯省赛题，风格是"重基础、代码重细节"，质数、约数、质因数分解类题目几乎年年出现；电子学会 C/C++ 考级四级及以上、Python 考级三级及以上，数论基础也是必考能力点；全国青少年信息素养大赛的算法挑战同样离不开"先筛素数、再分解、最后统计"的套路。

很多同学一遇到"求第 k 个质数""统计区间质数个数""求一个数的最大质因子"就只会for循环暴力试除，一旦数据上到 10⁶ 就超时。今天我们把这套最稳的板子一次讲透。

二、原创题目：校园质数能量站

【题目描述】
校园科技节布置了一排"质数能量站"。共有 n 个能量水晶，第 i 个水晶上写着一个正整数 aᵢ。
对于每个水晶，需要求出它的最大质因子（若该数等于 1，则最大质因子记为 0）。
请你输出这 n 个最大质因子的总和。
【输入格式】
第一行一个整数 n（1 ≤ n ≤ 10⁵）。
第二行 n 个整数 a₁, a₂, …, aₙ（1 ≤ aᵢ ≤ 10⁶）。
【输出格式】
一个整数，表示所有最大质因子之和。
【样例输入】
4 12 17 1 100
【样例输出】
25
【样例说明】
12 = 2² × 3，最大质因子为 3；17 是质数，最大质因子为 17；1 没有质因子，记为 0；100 = 2² × 5²，最大质因子为 5。3 + 17 + 0 + 5 = 25。

三、核心考点

质数判定与筛法：朴素试除 O(√a) 太慢；埃氏筛 O(N log log N) 可一次性求出 [1, N] 内所有质数；线性筛（欧拉筛）O(N) 一步到位。
最小质因子数组minPrime：线性筛的副产品——minPrime[x]记录 x 的最小质因子，是后续 O(log x) 分解的关键。
质因数分解：利用minPrime链，每个数反复除以其最小质因子，分解复杂度从 O(√x) 降到 O(log x)。
约数个数 / 约数和公式（进阶）：d(n) = Π(eᵢ + 1)，σ(n) = Π(pᵢ^{eᵢ+1}−1)/(pᵢ−1)。
复杂度与边界：数组开到MAXN = 10⁶+5，乘法用long long防溢出。

四、解法拆解

思路一：埃氏筛（最直观）

把 2 到 √N 的每个质数，划掉它的所有倍数。剩下的就是质数。

#include <iostream> #include <vector> using namespace std; const int MAXN = 1000005; bool isPrime[MAXN]; void eratosthenes(int n) { for (int i = 2; i <= n; ++i) isPrime[i] = true; for (long long i = 2; i * i <= n; ++i) { // 只用质数去划倍数 if (isPrime[i]) { for (long long j = i * i; j <= n; j += i) isPrime[j] = false; } } }

埃氏筛已能数出 [1, N] 内质数个数（蓝桥杯经典填空题"第 2026 个质数"也能解），但不能直接给出最小质因子，分解仍需配合试除。

思路二：线性筛（欧拉筛，本文主力）

每个合数只被它的最小质因子筛掉一次，因此达到 O(N) 线性时间，并且顺手记录minPrime。

#include <iostream> #include <vector> using namespace std; const int MAXN = 1000005; int minPrime[MAXN]; // minPrime[x] = x 的最小质因子，0 表示是质数 vector<int> primes; void linear_sieve(int n) { for (int i = 2; i <= n; ++i) { if (minPrime[i] == 0) { // i 是质数 minPrime[i] = i; primes.push_back(i); } for (int j = 0; j < (int)primes.size(); ++j) { long long np = 1LL * i * primes[j]; if (np > n) break; // 越界则停止 minPrime[np] = primes[j]; // 用最小质因子标记 if (i % primes[j] == 0) break; // 关键：保证每个合数只被最小质因子筛一次 } } }

if (i % primes[j] == 0) break;是线性筛的灵魂：一旦发现primes[j]能整除i，说明primes[j]已经是i的最小质因子，再往后的质数都不是i * primes[j]的最小质因子了，必须停下，否则合数会被重复筛。

思路三：用 minPrime 链 O(log x) 分解

不断除以当前数的最小质因子，最后一次除的那个就是最大质因子。

int max_prime_factor(int x) { if (x <= 1) return 0; // 1 没有质因子 int last = 0; while (x > 1) { int p = minPrime[x]; last = p; // 最后一次留下的就是最大质因子 x /= p; } return last; }

完整 C++ 参考代码（AC）

#include <iostream> #include <vector> using namespace std; const int MAXN = 1000005; int minPrime[MAXN]; vector<int> primes; void linear_sieve(int n) { for (int i = 2; i <= n; ++i) { if (minPrime[i] == 0) { minPrime[i] = i; primes.push_back(i); } for (int j = 0; j < (int)primes.size(); ++j) { long long np = 1LL * i * primes[j]; if (np > n) break; minPrime[np] = primes[j]; if (i % primes[j] == 0) break; } } } int max_prime_factor(int x) { if (x <= 1) return 0; int last = 0; while (x > 1) { int p = minPrime[x]; last = p; x /= p; } return last; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); linear_sieve(1000000); // 一次性建表 int n; cin >> n; long long ans = 0; // 用 long long 防溢出 for (int i = 0; i < n; ++i) { int x; cin >> x; ans += max_prime_factor(x); } cout << ans << "\n"; return 0; }

完整 Python 参考代码

MAXN = 1000005 min_prime = [0] * MAXN primes = [] def linear_sieve(n): for i in range(2, n + 1): if min_prime[i] == 0: min_prime[i] = i primes.append(i) for p in primes: np = i * p if np > n: break min_prime[np] = p if i % p == 0: break def max_prime_factor(x): if x <= 1: return 0 last = 0 while x > 1: p = min_prime[x] last = p x //= p return last linear_sieve(1000000) n = int(input()) a = list(map(int, input().split())) print(sum(max_prime_factor(x) for x in a))

五、时间 / 空间复杂度

建表（线性筛）：时间 O(N)，空间 O(N)，N = 10⁶ 时也仅需约 4 MB 的int数组，轻松放下。
单次分解：沿minPrime链，每步至少把 x 除以一个 ≥2 的质数，故 O(log x)。
总复杂度：O(N + n·log aᵢ)，n = 10⁵、aᵢ ≤ 10⁶ 时运行时间在毫秒级，远优于朴素试除的 O(n·√aᵢ)。

六、易错点（踩坑必看）

线性筛的 break 漏写：少了if (i % primes[j] == 0) break;，合数会被多个质因子重复筛，时间退化甚至出错。
数组越界：aᵢ最大 10⁶，minPrime必须开到MAXN = 10⁶+5；筛里np = i * primes[j]要用long long防中间溢出。
1 的特殊处理：题目明确 1 的最大质因子记为 0，漏判会返回minPrime[1]（未初始化为 0 的脏值）。
Python 列表 vs 全局变量：把min_prime设成全局列表，建表函数直接改它，避免函数参数拷贝大数组。
求和溢出：n 个最大质因子相加可能超过int，C++ 用long long，Python 无此忧。
分解死循环：while (x > 1)里必须执行x /= p，否则 x 不变会死循环。

七、进阶拓展

1. 约数个数与约数和
分解后套公式即可，蓝桥杯常把"求某个数的约数个数 / 约数和"作为填空或编程题：

long long divisor_count(int x) { // 约数个数 d(x)=Π(eᵢ+1) long long res = 1; while (x > 1) { int p = minPrime[x], e = 0; while (x % p == 0) { x /= p; e++; } res *= (e + 1); } return res; } long long divisor_sum(int x) { // 约数和 σ(x)=Π(pᵢ^{eᵢ+1}−1)/(pᵢ−1) long long res = 1; while (x > 1) { int p = minPrime[x], e = 0, pk = 1; while (x % p == 0) { x /= p; e++; pk *= p; } res *= (pk * p - 1) / (p - 1); } return res; }

2. 大区间质数筛（L, R 可达 10¹²）
当区间端点巨大、长度 ≤ 10⁶ 时，用"小素数筛大区间"：先筛出 √R 内的质数，再在区间 [L, R] 上打标记。这是电子学会 C/C++ 考级高级段、信息素养大赛算法挑战里的典型变形。

3. 顺手求欧拉函数 φ(n)
在线性筛里可以同时递推phi：i为质数时phi[i]=i-1；i % p == 0时phi[np]=phi[i]*p，否则phi[np]=phi[i]*(p-1)。一筛多得。

4. 超大数质因数分解（Pollard-Rho）
当 aᵢ 超过 10¹²，试除与筛都不够用时，可上基于生日悖论与素性测试（Miller–Rabin）的 Pollard-Rho 算法，蓝桥杯省赛提高组偶尔涉及，建议学有余力再攻克。