OneCoder Avatar
OneCodercoderli.com · 1026 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:从 O(√n) 试除法到埃氏筛、欧拉线性筛——为什么一行 break 能做到严格 O(n)?

📅 2026-11-21·✍️ OneCoder·计算中...·⏱️ 36 分钟

在质数判定与批量求质数的考场实战中,许多同学以为“质数很简单”,结果一交代码就撞上各种离奇失分:判单个大数是否为质数时,循环条件顺手写了 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 考场上,考生最常在以下三大痛点上丢分:

  1. “单数判质数忘拦 n < 2,或写 i * i <= n 暗藏溢出地雷”:把 1 误判为质数,或者在 n 接近 时因 i * i 超过 int 上限回绕成负数,酿成死循环与运行崩溃;
  2. “以为埃氏筛从 i * i 起筛就再无重复,说不清它与欧拉筛的差距”:虽然从 i * i 开始划倍数能省掉 3 * 2 = 6 这类较小倍数,但像 12、18、30 这类拥有多个不同质因数的合数依然会被反复覆盖标记多次,且若内层 int j = i * i 不防溢出,在 时会直接访问负数下标引发段错误(RE);
  3. “死背欧拉线性筛模板,没吃透 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 均绝对不溢出 考场必用 ✅
C++7 行
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)。古希腊数学家埃拉托斯特尼换了一个逆向思路:不再费力验证“谁是质数”,而是顺手把“每个质数的所有倍数”通通划掉,剩下的自然全是质数!

为了提速,标准埃氏筛包含两项经典优化:

  1. 只用质数去筛:若 i 已经被更小的数划掉(合数),它的所有倍数一定也早已被 i 的质因子划掉,直接跳过;
  2. 内层从 i * i 起跳:对于质数 i,比 i * i 小的倍数 2i, 3i, ..., (i - 1)i 都含有小于 i 的因子,早就在前面轮次被筛干净了,直接从 i * i 开始以步长 +i 向后标记(且外层只需枚举到 i <= n / i,彻底避免 i * i 溢出)。
C++13 行
// 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!

Code18 行
================================================================================
【埃氏筛 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. 证明【绝不重复】(每个合数最多被标记 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 精准掐断了所有“非最小质因数越权标记”的源头!
  2. 证明【绝不遗漏】(每个合数至少被标记 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 次) 批量打表首选;可顺手线性预处理最小质因数、约数个数、欧拉函数

💡 考场黄金法则:

  1. 【判单数用 i <= n / i,先拦 n < 2】:永不写 i * i <= n 或 sqrt(n),彻底消灭溢出与精度坑。
  2. 【线性筛先标后 break】:内层写 prime[j] <= n / i,先标记合数再判 i % prime[j] == 0,合数 x 只在 i = x / min_p 时被最小质因数唯一筛除!

🔍 二、 具象代码与数据推演(有举例)

示例:欧拉线性筛(n = 15)全流程拦截轨迹追踪

下面这段 23 行的标准 C++11 程序,对 n = 15 运行欧拉线性筛,实时打印每一个新收录的质数、每一次合数标记,以及触发 break 拦截的精确瞬间:

C++23 行
#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 次!

程序实际编译运行输出:

Code14 行
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 代码片段:

C++15 行
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
  • 解析过程:
    1. 锁定合数 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。
    2. 零手算秒求 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 均完全等价,不会产生任何运行结果或超时差异。( )

🔍 答案与反例证明:

  • 结论:错误(×)
  • 辨析证明:
    1. 数学等价不代表计算机有限字长下等价:在实数域中,对于正整数 ,不等式 确实与 等价;但在 32 位 int 寄存器中,乘法 i * i 可能突破上限 引发有符号整数溢出(未定义行为 UB),而除法 n / i 永远不会超出 n 本身。
    2. 极简反例:取 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 离奇地保持为真,循环失控继续飙升,最终引发死循环超时或运行崩溃!

【例题 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,表示一次查询。

输出格式: 对于每次查询,输出一行一个整数表示答案。

💡 算法建模与线性筛一箭双雕技巧:

  1. 用 min_p[x] 一举替代 is_comp[x]:不必单独开布尔数组 is_comp[],直接开全局静态数组 int min_p[10000005](自动清零,约占 40 MB 内存,严禁开在 main 局部栈内防爆栈)。规定 min_p[x] == 0 表示尚未被筛掉(即质数);
  2. 印证最小质因数唯一筛除定理:
    • 当外层走到 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!
  3. 时间与空间复杂度:预处理仅需严格 ( 时实测耗时不足 0.1 秒),每次查询直接 数组下标寻址返回 prime[x] 或 min_p[x],总时间复杂度 ,轻松满分通过。
C++43 行
#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
    29
    (样例解释:30 以内的质数依次为 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。)
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

GESP 编程与算法 · 五级⏱️ 26 分钟

【GESP/CSP考点精讲】GESP四级/五级 / CSP-J 必背:递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?

为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...

阅读全文 →
GESP 编程与算法 · 五级⏱️ 31 分钟

【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 编程与算法 · 五级⏱️ 33 分钟

【GESP/CSP考点精讲】GESP五级 / CSP-J 必背:分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计

当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...

阅读全文 →
OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!