C++ 算法考级专栏
🎨 视觉封面【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:从 O(√n) 试除法到埃氏筛、欧拉线性筛——为什么一行 break 能做到严格 O(n)?
在质数判定与批量求质数的考场实战中,许多同学以为“质数很简单”,结果一交代码就撞上各种离奇失分:判单个大数是否为质数时,循环条件顺手写了 i * i <= n,碰上 32 位最大梅森素数 2147483647 时 46341 * 46341 瞬间撑爆 int 回绕成负数,程序直接陷入死循环超时;题目要求在 1 秒内找出 以内的全部质数,还在用 逐个试除,评测机直接给出满屏 TLE;好不容易背下了欧拉线性筛的十几行代码,到了 CSP-J 初赛阅读程序题,出题人追问“合数 18 是在外层变量 i 等于几时被哪个质数筛掉的?”或者“把 if (i % prime[j] == 0) break; 挪到标记语句前面会怎样?”,立刻答不上来!在 GESP 五级认证以及 CSP-J/S 初复赛中, 试除法的 i <= n / i 防溢出写法、埃拉托斯特尼筛法 的原理与重复标记瓶颈、以及欧拉线性筛借助一行 break 保证每个合数仅被最小质因数唯一筛除的严格 数学证明,是初等数论模块最核心的分水岭。本文将从数学本质出发,把这三代质数算法的演进逻辑一次性讲透。
🎯 考纲锚点与核心痛点
📍 对应考点:掌握质数与合数的判定方法、试除法 优化、埃拉托斯特尼筛法 与欧拉线性筛 的算法原理、代码模板及复杂度分析。 🎯 适用等级:
GESP 五级考点 | CSP-J/S 初赛/复赛必考
在历年 GESP 五级真题与 CSP-J 考场上,考生最常在以下三大痛点上丢分:
- “单数判质数忘拦
n < 2,或写i * i <= n暗藏溢出地雷”:把1误判为质数,或者在n接近 时因i * i超过int上限回绕成负数,酿成死循环与运行崩溃; - “以为埃氏筛从
i * i起筛就再无重复,说不清它与欧拉筛的差距”:虽然从i * i开始划倍数能省掉3 * 2 = 6这类较小倍数,但像12、18、30这类拥有多个不同质因数的合数依然会被反复覆盖标记多次,且若内层int j = i * i不防溢出,在 时会直接访问负数下标引发段错误(RE); - “死背欧拉线性筛模板,没吃透
if (i % prime[j] == 0) break;的数学灵魂”:一旦题目要求改造筛法(如顺带统计每个数的最小质因数、质因数个数,或初赛追踪中间状态),缺乏对“最小质因数唯一筛除定理”的理解便寸步难行。
🧠 一、 核心原理深度拆解(有理论)
1. 单数判质数:成对约数对称性与 i <= n / i 防溢出机制
根据数学定义:质数(素数)是指大于 1 的自然数中,除了 1 和它自身外没有其他正因数的数。特别注意:0 和 1 既不是质数,也不是合数。
如果一个大于 1 的整数 n 是合数,那么它必能分解为两个正整数的乘积 (满足 )。由乘积对称性立得:
换句话说:合数的约数总是以 为对称轴成对出现。只要在 区间内找不到能整除 n 的因子,那么在 区间内也绝不可能存在因子,从而把单次判定时间复杂度从暴力 骤降至 !
但在把条件 翻译成 C++ 循环代码时,下面三种写法存在天壤之别:
| 写法对比 | 循环边界条件 | 底层运行隐患剖析 | 考场推荐度 |
|---|---|---|---|
| 浮点开方写法 | i <= sqrt(n) |
每次循环反复调用浮点函数开销大,且极大整数转 double 可能产生舍入精度偏差 |
不推荐 ⚠️ |
| 高危乘法写法 | i * i <= n |
当 n = 2147483647()时,i = 46341 的平方 2147488281 爆 int 变负数 -2147479015,循环条件继续为真导致死循环 |
严禁使用 ❌ |
| 满分除法写法 | i <= n / i |
全程纯整数运算,零浮点误差;右侧 n / i 只减不增,对任意 int 或 long long 均绝对不溢出 |
考场必用 ✅ |
bool is_prime(int n) {
if (n < 2) return false; // 铁律:先拦 0、1 与负数
for (int i = 2; i <= n / i; i++) { // 等价于 i <= floor(sqrt(n)),永不溢出
if (n % i == 0) return false;
}
return true;
}2. 埃拉托斯特尼筛法(埃氏筛):批量打表与 的秘密
当题目要求找出 [1, n](例如 n = 10^6 或 10^7)内的全部质数时,对每个数分别跑一遍 试除的总耗时高达 (n = 10^6 时运算量已达 级别,必 TLE)。古希腊数学家埃拉托斯特尼换了一个逆向思路:不再费力验证“谁是质数”,而是顺手把“每个质数的所有倍数”通通划掉,剩下的自然全是质数!
为了提速,标准埃氏筛包含两项经典优化:
- 只用质数去筛:若
i已经被更小的数划掉(合数),它的所有倍数一定也早已被i的质因子划掉,直接跳过; - 内层从
i * i起跳:对于质数i,比i * i小的倍数2i, 3i, ..., (i - 1)i都含有小于i的因子,早就在前面轮次被筛干净了,直接从i * i开始以步长+i向后标记(且外层只需枚举到i <= n / i,彻底避免i * i溢出)。
// is_comp[x] == true 表示 x 是合数(或非质数),false 表示质数
bool is_comp[1000005];
void eratosthenes_sieve(int n) {
is_comp[0] = is_comp[1] = true;
for (int i = 2; i <= n / i; i++) {
if (!is_comp[i]) {
for (int j = i * i; j <= n; j += i) {
is_comp[j] = true;
}
}
}
}(1)为什么时间复杂度是 而不是 ?
如果对 [2, n] 里的每个整数都划一遍倍数,总操作数是调和级数 ,复杂度为 。而埃氏筛只在 i 是质数时才启动内层循环,总标记次数为:
数论中著名的梅滕斯第二定理证明了质数倒数和的渐进阶为 ,增长极其缓慢(哪怕 n = 10^7,),因此埃氏筛的时间复杂度是接近线性的 !
(2)埃氏筛的唯一遗憾:依然存在“重复标记”
很多初学者误以为“内层从 i * i 开始就彻底消灭了重复标记”。其实不然!只要一个合数同时拥有多个不同质因子,它就难逃被反复划掉的命运:
- 以
12 = 2 × 2 × 3为例:i = 2时从4起步划掉了12;轮到i = 3时从9起步(9 <= 12),12被第二次标记; - 以
30 = 2 × 3 × 5为例:它在i = 2(起步4)、i = 3(起步9)、i = 5(起步25)时,被连环重复标记了整整 3 次!
3. 欧拉线性筛(Euler Sieve):一行 break 做到严格 的数学证明
如何把埃氏筛里的“重复标记”压缩到绝对零重复——让 [2, n] 里的每一个合数有且仅有 1 次被标记,从而把时间复杂度推向理论极限 ?
答案只有一句话:给每个合数指定唯一的“处决者”——规定任何合数 x 只允许被它的“最小质因数(SPF)”筛掉!
设合数 x 的最小质因数为 p,将其拆解为 x = i * p(其中 i = x / p)。由于 p 已经是 x 的最小质因数,商 i 的所有质因数必定都大于等于 p。欧拉线性筛巧妙地反向利用了这一性质:外层从小到大枚举商 i,内层从小到大枚举已找到的质数 prime[j] 去乘 i 筛掉合数 i * prime[j],并在发现 i % prime[j] == 0 时立刻 break!
================================================================================
【埃氏筛 vs 欧拉线性筛:为什么合数 12 与 18 绝不会被重复筛除?】
▶ 埃氏筛(按“质数倍数”硬扫,多质因子合数反复挨刀):
质数 2 扫过: 4, 6, 8, 10, [12], 14, 16, [18], 20 ...
质数 3 扫过: 9, [12], 15, [18], 21 ... <-- 12 和 18 被重复筛 2 次!
▶ 欧拉线性筛(按“商 i × 最小质因数 p”精准点杀):
i = 4 (已知质数 2, 3):
j=0, p=2: 筛掉 4 × 2 = 8 (最小质因数就是 2 ✅)
检查 4 % 2 == 0 ──▶ 立即 BREAK!
[拦截成功!] 坚决不筛 4 × 3 = 12(因为 12 的最小质因数是 2,轮不到 3 动手!)
i = 6 (已知质数 2, 3, 5):
j=0, p=2: 筛掉 6 × 2 = 12 (最小质因数就是 2 ✅,12 终于被正主唯一筛除!)
检查 6 % 2 == 0 ──▶ 立即 BREAK!
[拦截成功!] 坚决不筛 6 × 3 = 18(18 留给未来 i = 9 时由 9 × 2 = 18 唯一筛除!)
================================================================================严谨的双向数学证明(既不重复,也不遗漏)
为什么只需加上 if (i % prime[j] == 0) break;,就能保证每个合数被精确标记 1 次?我们分两步完成充要证明:
-
证明【绝不重复】(每个合数最多被标记 1 次): 因为每个合数的最小质因数
p是唯一的,所以拆法x = (x / p) * p也是唯一的——我们只需证明,循环内每次执行is_comp[i * prime[j]] = true时,prime[j]永远是乘积i * prime[j]的最小质因数:- 若此前所有更小的质数
prime[0 .. j-1]都不能整除i,说明i的最小质因数一定>= prime[j];因此把i乘上prime[j]后,新合数i * prime[j]的最小质因数恰好就是prime[j]! - 一旦首次出现
i % prime[j] == 0,说明prime[j]就是i的最小质因数。若不break继续看下一个更大的质数prime[j+1](显然prime[j+1] > prime[j]),由于i已经包含因子prime[j],乘积i * prime[j+1]的最小质因数其实是prime[j]而非prime[j+1]!它理应在以后商等于i' = (i / prime[j]) * prime[j+1]时被真正的最小质因数prime[j]筛掉。因此此处break精准掐断了所有“非最小质因数越权标记”的源头!
- 若此前所有更小的质数
-
证明【绝不遗漏】(每个合数至少被标记 1 次): 任取
[2, n]内的任意合数x,设其最小质因数为p,令商i = x / p。由于x是合数且p是最小质因数,必满足2 <= p <= i < x,且i绝不含任何小于p的质因子。- 因为
p <= i,当外层循环推进到i时,质数p早已收入prime[]数组; - 内层从小到大扫描所有小于
p的质数时,因为它们都无法整除i,所以绝不会提前触发break; - 当内层走到
prime[j] == p时,由于i * p = x <= n,条件prime[j] <= n / i必然成立,于是合数x在此刻被稳稳筛掉!
- 因为
既然 [2, n] 内的每个合数都被严格标记 1 次,且外层循环跑完 2..n 仅 n - 1 步,整个欧拉线性筛的总操作次数严格为 !
三大质数算法横向终极对比
| 算法名称 | 单次判质 / 批量筛 [1, n] 复杂度 |
空间复杂度 | 重复标记合数? | 核心优势与考场选型建议 |
|---|---|---|---|---|
| 试除法 | 单次 / 批量 | O(1) |
不涉及 | 只判断少量极大数(如 )时唯一选择,无需开大数组 |
| 埃氏筛 | 批量 | O(n) |
会重复 | 代码仅 6 行极简好写; 时常数极小,与线性筛速度几乎持平 |
| 欧拉线性筛 | 批量严格 | O(n) |
零重复(仅 1 次) | 批量打表首选;可顺手线性预处理最小质因数、约数个数、欧拉函数 |
💡 考场黄金法则:
- 【判单数用
i <= n / i,先拦n < 2】:永不写i * i <= n或sqrt(n),彻底消灭溢出与精度坑。- 【线性筛先标后
break】:内层写prime[j] <= n / i,先标记合数再判i % prime[j] == 0,合数x只在i = x / min_p时被最小质因数唯一筛除!
🔍 二、 具象代码与数据推演(有举例)
示例:欧拉线性筛(n = 15)全流程拦截轨迹追踪
下面这段 23 行的标准 C++11 程序,对 n = 15 运行欧拉线性筛,实时打印每一个新收录的质数、每一次合数标记,以及触发 break 拦截的精确瞬间:
#include <iostream>
using namespace std;
bool is_comp[20];
int prime[20];
int main() {
int n = 15, cnt = 0;
is_comp[0] = is_comp[1] = true;
for (int i = 2; i <= n; i++) {
if (!is_comp[i]) {
prime[cnt++] = i;
cout << "i=" << i << " [Prime] -> prime[" << cnt - 1 << "]=" << i << endl;
}
for (int j = 0; j < cnt && prime[j] <= n / i; j++) {
is_comp[i * prime[j]] = true;
cout << " i=" << i << " * p=" << prime[j] << " -> mark " << i * prime[j];
if (i % prime[j] == 0) { cout << " (BREAK)" << endl; break; }
cout << endl;
}
}
return 0;
}分步内存变量变化与筛除拦截推演表
外层 i |
进入前 is_comp[i] |
当前质数表 prime[] |
内层 (p, 乘积) 标记操作 |
终止原因与核心剖析 |
|---|---|---|---|---|
2 |
false(质数) |
{2} |
p=2: 标 4 |
2 % 2 == 0 触发 BREAK |
3 |
false(质数) |
{2, 3} |
p=2: 标 6;p=3: 标 9 |
3 % 3 == 0 触发 BREAK |
4 |
true(合数) |
{2, 3} |
p=2: 标 8 |
4 % 2 == 0 触发 BREAK:精准拦截 4 * 3 = 12! |
5 |
false(质数) |
{2, 3, 5} |
p=2: 标 10;p=3: 标 15 |
下一个 p=5 时 5 > 15 / 5 = 3,超界退出 |
6 |
true(合数) |
{2, 3, 5} |
p=2: 标 12 |
6 % 2 == 0 触发 BREAK:12 由最小质因数 2 唯一筛掉! |
7 |
false(质数) |
{2, 3, 5, 7} |
p=2: 标 14 |
下一个 p=3 时 3 > 15 / 7 = 2,超界退出 |
8..10 |
true(合数) |
{2, 3, 5, 7} |
无操作(prime[0]=2 > 15 / i) |
2 * 8 = 16 > 15,直接跳过内层循环 |
11, 13 |
false(质数) |
{2, 3, 5, 7, 11, 13} |
无操作(最小倍数已超 15) |
顺次收齐最后两个质数 11、13 |
核对结果:[2, 15] 共 14 个数,收录 6 个质数(2, 3, 5, 7, 11, 13),标记 8 个合数(4, 6, 8, 9, 10, 12, 14, 15),每个合数不多不少刚好只出现 1 次!
程序实际编译运行输出:
i=2 [Prime] -> prime[0]=2
i=2 * p=2 -> mark 4 (BREAK)
i=3 [Prime] -> prime[1]=3
i=3 * p=2 -> mark 6
i=3 * p=3 -> mark 9 (BREAK)
i=4 * p=2 -> mark 8 (BREAK)
i=5 [Prime] -> prime[2]=5
i=5 * p=2 -> mark 10
i=5 * p=3 -> mark 15
i=6 * p=2 -> mark 12 (BREAK)
i=7 [Prime] -> prime[3]=7
i=7 * p=2 -> mark 14
i=11 [Prime] -> prime[4]=11
i=13 [Prime] -> prime[5]=13⚡ 三、 考场高频避坑指南(正误辨析)
在 GESP 五级判断题与 CSP-J 考场上,以下三个边界陷阱最容易导致整题失分:
❌ 易错点 1:把 if (i % prime[j] == 0) break; 错写在 is_comp[i * prime[j]] = true; 前面!
- 错误代码:
C++4 行
for (int j = 0; j < cnt && prime[j] <= n / i; j++) { if (i % prime[j] == 0) break; // 致命顺序颠倒! is_comp[i * prime[j]] = true; } - 为什么错:如果先判
break再做标记,当外层i = 2时,2 % 2 == 0直接跳出循环,连4 = 2 × 2都没有被标记为合数!紧接着i = 3漏筛9 = 3 × 3,i = 5漏筛25 = 5 × 5——所有质数的平方 以及形如 的合数会瞬间全军覆没,彻底破坏算法正确性! - 正确规范:牢记
i * prime[j]的最小质因数依然是prime[j],我们拦截的是下一轮更大的prime[j + 1],所以永远是先执行标记,再判断break!
❌ 易错点 2:筛法结束后忘记初始化 is_comp[0] = is_comp[1] = true,把 1 错判成质数!
- 错误认知:全局数组
bool is_comp[MAXN];默认全为false,跑完从i = 2到n的埃氏筛或欧拉筛后,直接拿!is_comp[x]当作x是否为质数的查询结果。 - 为什么错:无论是埃氏筛还是欧拉筛,外层循环都是从
i = 2起步,全程根本不会去修改is_comp[0]和is_comp[1]!它们一直保持着初始值false。只要测试数据里混进一个x = 1或x = 0,!is_comp[1]就会返回true,把1堂而皇之地当成质数计入答案,直接 WA! - 正确规范:筛法函数开头第一行养成肌肉记忆,显式写死
is_comp[0] = is_comp[1] = true;。
❌ 易错点 3:在 规模下,筛法内层写 int j = i * i 或 i * prime[j] <= n 导致 32 位 int 溢出 RE!
- 错误代码:埃氏筛里把外层写成了
for (int i = 2; i <= n; i++)(没限i <= n / i),内层直接for (int j = i * i; j <= n; j += i);或者欧拉筛内层写i * prime[j] <= n(当 、质数较大时两int相乘超 )。 - 为什么错:当
i = 50003(质数)时,i * i = 2500300009超过了 32 位有符号整数上限2147483647,溢出回绕成一个巨大的负数-1794667287!接着j <= n判定为真,程序执行is_comp[-1794667287] = true疯狂写入非法内存地址,当场触发 Segmentation Fault(段错误 RE)! - 正确规范:埃氏筛外层严格限制
i <= n / i(若要顺带统计所有质数,则只当i <= n / i时才进内层,或内层下标改用long long);欧拉筛内层边界条件永远用除法写法prime[j] <= n / i!
📝 四、 真题实战演练与精析(有例题:3 道)
【例题 1 · 单选题】(CSP-J 初赛 / GESP 五级阅读程序经典考点:欧拉线性筛轨迹与标记次数精确统计)
题目:阅读以下标准欧拉线性筛 C++11 代码片段:
int cnt = 0, mark_cnt = 0;
bool is_comp[25] = {};
int prime[25] = {};
void sieve(int n) {
is_comp[0] = is_comp[1] = true;
for (int i = 2; i <= n; i++) {
if (!is_comp[i]) prime[cnt++] = i;
for (int j = 0; j < cnt && prime[j] <= n / i; j++) {
is_comp[i * prime[j]] = true;
mark_cnt++;
if (i % prime[j] == 0) break;
}
}
}当调用 sieve(20) 时,合数 18 是在 (i, prime[j]) 取何值时被筛掉的?且整个函数运行结束后,计数器 mark_cnt 的值是多少?( )
- A.
i = 6, prime[j] = 3;mark_cnt = 11 - B.
i = 6, prime[j] = 3;mark_cnt = 13 - C.
i = 9, prime[j] = 2;mark_cnt = 11 - D.
i = 9, prime[j] = 2;mark_cnt = 12
🔍 答案与逐项排除解析:
- 正确答案:C
- 解析过程:
- 锁定合数
18的唯一筛除时刻(排除 A、B):根据欧拉线性筛核心定理,每个合数只被它的最小质因数唯一筛除。分解 ,其最小质因数显然是2,对应的商为 。因此18一定是在i = 9, prime[j] = 2时被筛掉的!为什么不是i = 6, prime[j] = 3?因为当i = 6时,内层先用prime[0] = 2筛掉6 * 2 = 12,紧接着6 % 2 == 0立刻触发break,根本不会执行到prime[1] = 3!由此直接秒杀排除 A、B。 - 零手算秒求
mark_cnt(排除 D):利用“每个合数有且仅被标记 1 次”的数学性质,无需逐轮硬模拟循环!区间[2, 20]共有20 - 1 = 19个正整数,其中质数有2, 3, 5, 7, 11, 13, 17, 19共8个,因此合数恰好有19 - 8 = 11个。每个合数恰好让mark_cnt自增 1 次,故函数结束时mark_cnt严格等于11!故锁定 C。
- 锁定合数
【例题 2 · 判断题】(GESP 五级数论边界辨析:i * i <= n 与 i <= n / i 是否完全等价?)
题目:在 C++11 标准(int 为 32 位有符号整数,范围为 )下,编写单数判质数函数 bool is_prime(int n)(假设已先处理 if (n < 2) return false;)时,循环条件 for (int i = 2; i * i <= n; i++) 与 for (int i = 2; i <= n / i; i++) 对任意合法的 int 正整数输入 n 均完全等价,不会产生任何运行结果或超时差异。( )
🔍 答案与反例证明:
- 结论:错误(×)
- 辨析证明:
- 数学等价不代表计算机有限字长下等价:在实数域中,对于正整数 ,不等式 确实与 等价;但在 32 位
int寄存器中,乘法i * i可能突破上限 引发有符号整数溢出(未定义行为 UB),而除法n / i永远不会超出n本身。 - 极简反例:取 32 位
int的最大值n = 2147483647(它恰好是著名的第 8 个梅森素数 ,不存在任何真因子)。- 循环执行到
i = 46340时,,无法整除; - 下一轮
i递增为46341:在i <= n / i写法下,2147483647 / 46341 = 46340,条件46341 <= 46340为假,循环正常终止并返回true; - 而在
i * i <= n写法下,真实平方值 ,在主流补码环境下溢出回绕为负数-2147479015,使得i * i <= n离奇地保持为真,循环失控继续飙升,最终引发死循环超时或运行崩溃!
- 循环执行到
- 数学等价不代表计算机有限字长下等价:在实数域中,对于正整数 ,不等式 确实与 等价;但在 32 位
【例题 3 · 微代码实战】(GESP 五级 / CSP-J 复赛高频母题:线性筛 预处理第 k 小质数与最小质因数)
题目描述:给定正整数上限 n()以及 q()次查询。每次查询给出两个整数 op 和 x:
- 当
op == 1时,输出[1, n]范围内第x小的质数(数据保证x不超过范围内的质数总个数); - 当
op == 2时,输出正整数x()的最小质因数(若x本身是质数,其最小质因数即为x自身)。
输入格式:
第一行包含两个正整数 n 和 q,分别表示筛法范围上限与查询次数。
接下来 q 行,每行包含两个正整数 op 和 x,表示一次查询。
输出格式: 对于每次查询,输出一行一个整数表示答案。
💡 算法建模与线性筛一箭双雕技巧:
- 用
min_p[x]一举替代is_comp[x]:不必单独开布尔数组is_comp[],直接开全局静态数组int min_p[10000005](自动清零,约占40 MB内存,严禁开在main局部栈内防爆栈)。规定min_p[x] == 0表示尚未被筛掉(即质数); - 印证最小质因数唯一筛除定理:
- 当外层走到
i发现min_p[i] == 0时,i必为质数,令min_p[i] = i并收入prime[++cnt] = i; - 在内层筛除合数
i * prime[j]时,由前文证明可知prime[j]必然就是它的最小质因数,因此直接赋值min_p[i * prime[j]] = prime[j];,随后若i % prime[j] == 0立即break!
- 当外层走到
- 时间与空间复杂度:预处理仅需严格 ( 时实测耗时不足 0.1 秒),每次查询直接 数组下标寻址返回
prime[x]或min_p[x],总时间复杂度 ,轻松满分通过。
#include <iostream>
using namespace std;
const int MAXN = 10000005;
const int MAXP = 700005; // 10^7 以内共有 664579 个质数
int min_p[MAXN]; // min_p[x] 记录 x 的最小质因数,初始全局清 0 表示未筛除
int prime[MAXP]; // prime[1..cnt] 按升序保存筛出的所有质数
int cnt = 0;
void euler_sieve(int n) {
for (int i = 2; i <= n; i++) {
if (min_p[i] == 0) {
min_p[i] = i;
prime[++cnt] = i;
}
// 用 prime[j] <= n / i 杜绝乘法溢出;先记录最小质因数,再判整除 break
for (int j = 1; j <= cnt && prime[j] <= n / i; j++) {
min_p[i * prime[j]] = prime[j];
if (i % prime[j] == 0) {
break;
}
}
}
}
int main() {
int n, q;
cin >> n >> q;
euler_sieve(n);
for (int i = 1; i <= q; i++) {
int op, x;
cin >> op >> x;
if (op == 1) {
cout << prime[x] << "\n";
} else {
cout << min_p[x] << "\n";
}
}
return 0;
}- 输入样例:
Code7 行
30 6 1 1 1 5 1 10 2 12 2 25 2 29 - 输出样例:
(样例解释:Code6 行
2 11 29 2 5 2930以内的质数依次为2, 3, 5, 7, 11, 13, 17, 19, 23, 29,因此第1、第5、第10小的质数分别是2、11、29;合数12在i = 6时被最小质因数2标记min_p[12] = 2,合数25在i = 5时被标记min_p[25] = 5,质数29的最小质因数即自身29。)
所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP/CSP考点精讲】GESP四级/五级 / CSP-J 必背:递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?
为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:从 O(2^n) 到 O(n) 的奇迹——重叠子问题与记忆化搜索
为什么一段只有 5 行的斐波那契递归代码 return fib(n - 1) + fib(n - 2);,当输入 n = 10 时瞬间出解,一旦输入 n = 45 就会触发超过 22 亿次函数调用,把评测机死死卡在 TLE(运行超时)?更神奇的是,为什么在不改变递归主体...
【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计
当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

