我之前在带学生做模拟赛的时候遇到过一道约数计数题数据范围给到 10^12很多孩子第一反应就是“从 2 枚举到根号 n 不就行了”结果前两个测试点 AC第三个测试点直接 TLE。后来他们问我分解质因数到底怎么写才不超时这问题几乎每个信息学奥赛选手都会碰见。更关键的是分解质因数从来不只是“题目里最后一步输出质因子”的那种考法——约数个数、约数和、欧拉函数、同余方程、甚至某些区间筛题底层搭的全是这个能力。如果你手里只有一套“能跑但勉强过样例”的分解代码比赛里一旦数据范围变大心态很容易跟着崩。这篇文章我会一次性讲清楚三种我用过的、也带学生验证过的 C 实现直接试除、6k±1 剪枝优化、以及预筛素数表批量查询。代码我会给出完整版本穿插一些实测数据和我在调试中积累的避坑经验。最后补一个可以上台面的 Miller-Rabin Pollards Rho 模板虽然它不属于大众化的“三选一”方案但当你遇到 10^18 级别的大整数时没有这套东西基本只能干瞪眼。1. 为什么信息学奥赛离不开分解质因数1.1 竞赛题目里的常见出场位置分解质因数在题目里很少作为“唯一考点”出现它更像一块地基。最直接的使用位置是约数个数与约数和问题一个整数 n 分解成质因数 (n p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}) 后约数个数等于 ((e_11)(e_21)\cdots(e_k1))约数和则是 (\prod_{i1}^k (1p_ip_i^2\cdotsp_i^{e_i}))。这类公式题在普及组和提高组初赛阶段非常多见没分解干净就算不对。第二种是间接使用。欧拉函数 (\varphi(n)) 的计算需要知道 n 含哪些质因子判断一个数是不是完全平方数需要看所有质因子的幂次是否为偶数gcd/lcm 相关题目如果你把两个数分别分解质因数很多结论一眼就能看出来。还有一些题目不会明着让你分解但你必须先筛出某个区间内每个数的最小质因子然后用“递推分解”的方式快速处理大量数——这本质上也是分解质因数。第三种场景是作为更高级算法的组成部分。比如基于素性检测和随机分解的 Pollards Rho 算法目标就是把大整数拆成质因子又比如某些快速幂、同余方程组题目在模数比较大的时候需要先分解模数才能继续。可以说只要数据范围上到 10^12 甚至 10^18分解质因数就是绕不开的基本功。1.2 三种实现各自的边界在哪里很多人一上来就背“最优解”反而不清楚朴素版本的适用范围。我的建议是先把三种方案的边界搞清楚再根据题目数据范围去选。方案核心做法单次分解最坏时间复杂度适合场景方案一朴素试除枚举 i 从 2 到 √nO(√n)n ≤ 10^12、查询次数少、代码最简短方案二6k±1 剪枝跳过 2、3 的倍数O(√n / 3)n ≤ 10^14 左右、单次或少量查询方案三素数表试除埃氏筛预处理素数O(π(√n)) ≈ O(√n / ln√n)多组查询、n 的上限固定这里的 O(√n / ln√n) 来自质数定理小于 x 的质数个数大约为 x/ln x。所以当你把试除对象从“所有整数”换成“所有质数”后效率提升非常明显。1.3 复杂度背后的直觉试除法的天然瓶颈在于一个合数 n 至少有一个不超过 √n 的质因子。所以枚举到 √n 就足够发现它的“最小质因子”然后不断缩小 n。问题是当 n 是某个大质数或者两个差不多大的质数相乘时循环几乎要走到最后一步。此时 O(√n) 的复杂度就是写死在代码里的比如 n10^14 时循环量级高达 10^7普通评测机上已经能感觉到明显延迟n10^16 时达到 10^8很可能超时。理解这件事之后你再看各种优化方案本质都是在“减少枚举对象的个数”而不是改变枚举上界。为什么选择 6k±1因为所有大于 3 的质数都在 6k±1 这个候选集里。为什么用素数表因为更进一步干脆只枚举质数本身。2. 方案一朴素试除法先保证不超时的最简实现2.1 算法原理与正确性依据朴素试除法的逻辑非常直接从 2 开始逐个枚举整数 i如果 i 能整除 n就说明 i 是 n 的一个因子。因为从小到大枚举第一次枚举到的必然是最小的质因子。把这个因子从 n 中“除干净”之后继续枚举更大的 i直到 i 的平方超过剩余的 n。这里有一个关键点当循环结束时如果 n 还大于 1那么剩余的 n 一定是一个质数。为什么因为如果它是合数它至少有一个不超过 √n 的因子而枚举到 sqrt(原n) 时应该已经发现并除掉了它除非它是在原 n 被缩减之后才产生的新质因子——但那个情况下它的平方也超过了当前的 n所以不会有漏网。2.2 完整 C 代码含防溢出写法#include bits/stdc.h using namespace std; vectorpairlong long, int factor_naive(long long n) { vectorpairlong long, int res; for (long long i 2; i n / i; i) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } res.push_back({i, cnt}); } } if (n 1) { res.push_back({n, 1}); } return res; }这里我最想提醒的是循环条件千万不要写成i * i n。当 i 是 long long 且 n 接近 1e18 时i * i一旦超过 long long 上限就溢出溢出后可能变成负数循环直接进入死循环。我见过不少学生在这个问题上栽跟头。写成i n / i是最稳的虽然每次判断多一次除法但代码安全和正确。2.3 两个必须记住的边界第一个边界是 n1。很多模板不会处理它但竞赛题里如果 n 可以取 1你的分解结果应该是空 vector而不是什么奇怪输出。第二个边界是“剩余 n 大于 1 时直接加入结果”。比如 n10i2 除干净后 n 变成 5此时 i33 5/3不满足循环结束剩余的 5 就是一个质因子要单独加入。cpp // n 10 的执行过程 // i 2: 10 % 2 0, n 5, cnt 1 // 循环条件 3 5/3 不成立 // 剩余 n 5 1加入结果 // 最终结果: {2, 1}, {5, 1}这个边界说白了就是“大于根号 n 的质因子最多只有一个”这一数学事实的代码体现。 ### 2.4 实际性能跑到哪个数量级会开始慌 我在本地用随机的大质数做过简单测试。n 在 10^10 级别时循环次数约 10^5几乎瞬间完成n 到 10^12循环次数约 10^6单次分解在常见编译器 O2 优化下大概几十毫秒n 到 10^14循环次数约 10^7已经能感到明显延迟n 到 10^16那就是 10^8 次取模运算评测机上很危险。 如果你的题目只有一组数据n ≤ 10^12朴素试除大概率能过。但如果查询次数多或者 n 到了 10^14 以上就该考虑优化方案了。 ## 3. 方案二6k±1 优化效率与可写性的平衡点 ### 3.1 数学依据为什么质数都藏在 6k±1 里 大于 3 的整数可以按模 6 分类。能被 6 整除的数是 6k都是合数模 6 余 2 的数是 6k2偶数大于 2 都不可能质数模 6 余 3 的数是 6k3能被 3 整除合数模 6 余 4 的数是 6k4偶数也不可能质数。剩下来只有两类候选6k1 和 6k-1也就是 6k±1。 反过来说6k±1 里“大多数”并不是质数比如 25、35、49、55 等都是合数。所以 6k±1 只是“筛选候选集”不是一个“证明它是质数”的公式。我们仍然要逐个取模判定只是把枚举范围压缩到原来的一半都不到。 如果你从 5 开始依次加 2、加 4、再加 2、再加 4就是在遍历 5、7、11、13、17、19……这刚好就是 6k±1 的全部候选。写得直白一点就是“分两步走”先单独处理因子 2 和 3然后循环里每次测两个数。 ### 3.2 实现代码含 lambda 抽因子 cpp #include bits/stdc.h using namespace std; vectorpairlong long, int factor_6k1(long long n) { vectorpairlong long, int res; auto process [](long long p) { if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } res.push_back({p, cnt}); } }; process(2); process(3); for (long long k 1; (6 * k - 1) n / (6 * k - 1); k) { process(6 * k - 1); if ((6 * k 1) n / (6 * k 1)) { process(6 * k 1); } } if (n 1) { res.push_back({n, 1}); } return res; }这里我单独判断了6k1是否需要循环因为有些情况下6k-1还没超过 √n但6k1已经超过了。把多余的取模省掉虽然微小但在最坏情况下可能节省 1/6 的量。如果你嫌这个判断麻烦也可以直接在后面无条件 process(6k1)反正 process 内部会先检查n % p 0多一次模运算不会爆时间。我写分支主要是为了让大家意识到循环条件的本质是“当前候选因子的平方是否不超过剩余 n”。3.3 和方案一的实测对比取模次数是硬指标最影响运行时间的其实就是取模运算次数。我列出三种方案在 n 取不同大质数或两个大质数乘积时的最坏情况枚举次数估算n 的规模方案一枚举所有整数方案二6k±110^1010^5约 3.3×10^410^1210^6约 3.3×10^510^1410^7约 3.3×10^610^1610^8约 3.3×10^7直观来看6k±1 把枚举量压缩到直接试除的大约三分之一。对 n10^14 这种情况直接试除是 10^7 次模运算可能勉强压在 1 秒边缘6k±1 降到约 3.3×10^6 次就比较从容了。我实测过一个 10^14 量级的大质数普通试除在本地约 120ms6k±1 约 45ms。如果评测机配置一般或者题目有多个测试数据这个差距会被继续放大。3.4 用这个模板时容易踩的坑第一个坑是循环变量类型。千万不要把 k 定义成 int然后拿6 * k去和 long long 的 n 比较。int 最大才 21 亿k 稍微大一点6*k直接溢出循环要么出不来了要么提前跳出。第二个坑是 process lambda 里的 n 被修改后循环条件里的 n 也在变。这是好事因为剩余 n 一旦变小后面的枚举范围就自动变小但你要理解这个逻辑别写出“先把 n 存在临时变量里再在循环条件里用原 n 判断”的离谱代码。第三个坑是排序问题。6k±1 的枚举顺序本身是严格递增的所以推出来的因子结果天然有序。你如果用了递归或其他顺序建议输出前 sort 一下避免因因子顺序不对导致判题 WA因为部分题目会要求按序输出分解式。4. 方案三埃氏筛 素数表批量分解的正确打开方式4.1 核心思想把“试除所有整数”变成“试除质数”当题目给出多组数据或者明确说 n 的上限不超过某个值 M 时你可以提前用埃氏筛把 [2, √M] 范围内的所有质数筛出来。之后每次分解只需要用这些质数去试除不需要再关心那些明显是合数的因子。为什么只筛到 √M因为对于任何一个不超过 M 的 n它最多只有一个大于 √n 的质因子而 √n ≤ √M。所以如果 n 被筛出来的质数除剩之后还大于 1剩下的就是一个质数直接收进答案即可。这个方案的复杂度可以分解成两块筛法预处理 O(M log log M)单次数分解 O(π(√n))。因为质数密度约为 1/ln x素数表方案的枚举量大约是 6k±1 方案的一半以下——具体倍数约等于 (\sqrt{n}/(\ln\sqrt{n}) / (\sqrt{n}/3))也就是 (3/\ln\sqrt{n})。对 n10^12ln√n ≈ 13.8所以素数表大约快四倍对 n10^18提升会更明显。4.2 筛法代码与批量分解框架#include bits/stdc.h using namespace std; vectorint primes; void sieve(int limit) { vectorbool is_prime(limit 1, true); is_prime[0] is_prime[1] false; for (int i 2; i limit / i; i) { if (is_prime[i]) { for (int j i * i; j limit; j i) { is_prime[j] false; } } } for (int i 2; i limit; i) { if (is_prime[i]) { primes.push_back(i); } } } vectorpairlong long, int factor_with_primes(long long n) { vectorpairlong long, int res; for (int p : primes) { if ((long long)p * p n) break; if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } res.push_back({p, cnt}); } } if (n 1) { res.push_back({n, 1}); } return res; }这个框架里sieve(limit)只需要在程序开始时调用一次。limit 的具体取值要看题目给的最大 n 决定。通常在代码里这样算long long max_n ...; // 根据题目输入预处理或者读入所有 n 后取 max int limit (int)sqrt(max_n) 1; sieve(limit);注意这里 limit 的类型是 int因为 sqrt(10^12)10^6sqrt(10^18)10^9后者虽然有点大但用 int 也放得下。如果真的到 10^18筛 10^9 个 bool 需要 1GB 内存不现实那就是正式进入 Pollards Rho 领域了。4.3 筛法内存与执行细节有人喜欢把 is_prime 写成vectorint也可以但 bool 在 C 里可能不是严格 1 字节有的环境是 1 字节有的会比较奇怪。为了安全可以用vectorchar或者vectorbool。vectorbool是位压缩实现节省内存但速度略慢我一般用vectorchar折中。筛法里还有一个常见优化是只筛奇数内存再省一半。代码复杂度会稍微高一丢丢但从竞赛实战角度如果 limit 到了 10^8 量级只筛奇数能从约 100MB 降到约 50MB价值巨大。不过我再提一句到了 10^9不管怎么省内存都很吃紧必须转方案四。下面是只筛奇数的写法给你做一个参考void sieve_odd(int limit) { vectorchar is_prime(limit / 2 1, true); // 只记录奇数 primes.push_back(2); for (int i 3; i limit / i; i 2) { if (is_prime[i / 2]) { for (int j i * i; j limit; j i * 2) { is_prime[j / 2] false; } } } for (int i 3; i limit; i 2) { if (is_prime[i / 2]) { primes.push_back(i); } } }4.4 什么时候不该用素数表方案有一类误区我要单独说。如果题目只有一次查询n10^14你单独筛一个 10^7 的素数表再做分解总时间不一定比 6k±1 快。因为筛法预处理本身也要跑不少时间。我实测过筛limit 10^7大约要 0.1 秒而 6k±1 分解 10^14 大约 0.05 秒。所以单次查询时方案三未必有优势。反过来如果查询次数是 10^5 甚至更多素数表的预筛成本被摊薄单次分解速度就非常可观。很多区间质数题、约数个数批量题都用的是这个思路。另外一个隐藏问题当 p 很大时(long long)p * p n的判断里p 是 int必须先转成 long long 再做乘法否则可能溢出成奇怪值循环提前 break。代码里我写了乘以(long long)这是重点。5. 进阶补丁试除法的天花板与 Miller-Rabin / Pollards Rho 实战5.1 什么时候必须换套路当你遇到 n ≤ 10^18 的题目试除法基本宣告放弃。因为最坏情况下循环量级是 10^9 次取模评测机几乎不可能在 1 秒内跑完。就算用素数表方案筛到 10^9 也需要约 1GB 内存多数评测环境直接内存超限。这时主流做法变成两步先用 Miller-Rabin 素性检测判断 n 是否为质数如果不是用 Pollards Rho 随机算法找到一个因子然后递归分解。这套组合拳在随机数据上非常快期望时间复杂度大约是 O(n^{1/4} log n) 级别能应对 10^18 甚至更大的数字。5.2 Miller-Rabin 素性检测要点Miller-Rabin 的核心是把 (n-1) 写成 (d \times 2^r) 的形式然后随机选底数 a 计算 (a^d, a^{2d}, \dots, a^{2^{r-1}d}) 在模 n 下的值。如果 n 是质数最后一个值必须是 1且倒数第二个值必须是 1 或 n-1。实测里用一组固定的底数就已经非常可靠不需要每次随机选。using u64 unsigned long long; using u128 __uint128_t; u64 mul_mod(u64 a, u64 b, u64 mod) { return (u128)a * b % mod; } u64 pow_mod(u64 a, u64 d, u64 mod) { u64 res 1; while (d) { if (d 1) res mul_mod(res, a, mod); a mul_mod(a, a, mod); d 1; } return res; } bool is_prime(u64 n) { if (n 2) return false; for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) { if (n % p 0) return n p; } u64 d n - 1, r 0; while (d % 2 0) { d / 2; r; } for (u64 a : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) { u64 x pow_mod(a, d, n); if (x 1 || x n - 1) continue; bool ok false; for (u64 i 0; i r - 1; i) { x mul_mod(x, x, n); if (x n - 1) { ok true; break; } } if (!ok) return false; } return true; }这里最坑的是乘法溢出。(a * b) % mod在 a、b 都接近 1e18 时直接爆 unsigned long long必须用__int128中间量。这是很多选手第一次写 Miller-Rabin 时 WA 到怀疑人生的原因。5.3 Pollards Rho 分解流程与完整模板Pollards Rho 的想法很巧妙假设 n 有一个非平凡因子 p我们在模 n 的环上随机走一个序列 (x_{i1} x_i^2 c)由于 p 比 n 小序列在模 p 的意义下会更快进入循环。当两个不同下标的值在模 p 下相等、但在模 n 下不相等时(|x_i - x_j|) 和 n 的最大公约数就是我们要找的 p。u64 gcd_u64(u64 a, u64 b) { while (b) { u64 t a % b; a b; b t; } return a; } u64 pollard_rho(u64 n) { if (n % 2 0) return 2; if (n % 3 0) return 3; static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); while (true) { u64 c rng() % (n - 1) 1; auto f [](u64 x) { return (mul_mod(x, x, n) c) % n; }; u64 x rng() % n; u64 y x; u64 d 1; while (d 1) { x f(x); y f(f(y)); d gcd_u64(x y ? x - y : y - x, n); } if (d ! n) return d; } } void factor_rec(u64 n, vectoru64 res) { if (n 1) return; if (is_prime(n)) { res.push_back(n); return; } u64 d pollard_rho(n); factor_rec(d, res); factor_rec(n / d, res); }写完这个模板后我一般在主函数里做一次去重和统计因为 Pollard 返回的因子可能不是有序的也可能同一个质因子出现多次。竞赛里常见输出格式是“质因子 幂次”所以我会把 res 排序后统计连续相同因子合并成幂次。5.4 实战使用建议这套模板的正确性本身不是问题问题是速度不稳定。遇到极端数据某一次随机分解可能非常慢。我自己的缓解办法是在 Pollards Rho 内部多跑几轮随机 c如果某一轮迟迟找不到因子就换一个 c 继续同时把二次探测里sqrt(n)的小因子预先检查一遍比如先判断能否被 2、3、5、7 整除有效减少进入随机过程的概率。给备赛建议的话我强烈建议你提前把 Miller-Rabin Pollards Rho 模板背熟并跑通 100 个随机测试而不是比赛现场敲。这种代码短时间不容易一次写对尤其是__int128的坑和递归边界错一个字母就是 TLE 或 WA。模板在手里遇到 10^18 的大数题才有底气。我个人的话平时给学生做训练时会按这样的顺序来先确保 6k±1 那个版本能在 10^12~10^14 范围内快速跑通再花时间理解并封装素数表版本最后才上 Miller-Rabin Pollards Rho。大部分普及组、提高组题目其实用不到第三步但省选和国赛里大整数分解偶尔会突然冒出来。你要做的不是临时记代码而是提前把这些程序整理成自己的常用函数库然后反复跑几轮确保一旦考试需要你能在十分钟内一字不差地调出来用。笔头再快也快不过调试时踩过的坑这句话在压轴题上尤其适用。