本文面向准备蓝桥杯省赛、中国电子学会青少年软件编程C/C、Python等级考试、全国青少年信息素养大赛算法挑战赛项的同学拆解一个被三大赛事共同高频考察、却最容易被忽视的基础模块质数筛法埃氏筛 / 线性筛与质因数分解。附原创练习题与 C / Python 双语言满分写法。一、为什么这篇值得刷翻看近年的蓝桥杯省赛题风格是重基础、代码重细节质数、约数、质因数分解类题目几乎年年出现电子学会 C/C 考级四级及以上、Python 考级三级及以上数论基础也是必考能力点全国青少年信息素养大赛的算法挑战同样离不开先筛素数、再分解、最后统计的套路。很多同学一遇到求第 k 个质数统计区间质数个数求一个数的最大质因子就只会for循环暴力试除一旦数据上到 10⁶ 就超时。今天我们把这套最稳的板子一次讲透。二、原创题目校园质数能量站【题目描述】校园科技节布置了一排质数能量站。共有 n 个能量水晶第 i 个水晶上写着一个正整数 aᵢ。对于每个水晶需要求出它的最大质因子若该数等于 1则最大质因子记为 0。请你输出这 n 个最大质因子的总和。【输入格式】第一行一个整数 n1 ≤ n ≤ 10⁵。第二行 n 个整数 a₁, a₂, …, aₙ1 ≤ aᵢ ≤ 10⁶。【输出格式】一个整数表示所有最大质因子之和。【样例输入】4 12 17 1 100【样例输出】25【样例说明】12 2² × 3最大质因子为 317 是质数最大质因子为 171 没有质因子记为 0100 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 表示是质数 vectorint 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]; vectorint 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 个最大质因子相加可能超过intC 用long longPython 无此忧。分解死循环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)在线性筛里可以同时递推phii为质数时phi[i]i-1i % p 0时phi[np]phi[i]*p否则phi[np]phi[i]*(p-1)。一筛多得。4. 超大数质因数分解Pollard-Rho当 aᵢ 超过 10¹²试除与筛都不够用时可上基于生日悖论与素性测试Miller–Rabin的 Pollard-Rho 算法蓝桥杯省赛提高组偶尔涉及建议学有余力再攻克。八、小结与互动质数筛与质因数分解是蓝桥杯、电子学会 C/C 与 Python 考级、全国青少年信息素养大赛共同的基础底盘。记住两句话线性筛一句话灵魂是i % primes[j] 0就 break分解一句话灵魂是沿minPrime链反复除到底最后留下的是最大质因子。把上面的板子背熟、自己敲三遍再遇到质数 / 约数 / 分解类题基本能稳稳拿下。互动时间你练蓝桥杯或电子学会考级时还被哪些数论 / 算法考点卡过欢迎在评论区留言下一篇我们挑最高频的来讲。如果觉得有用点个赞 收藏关注我持续更新少儿编程算法干货 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。