不需要从零写大整数；对64位整数，用unsigned long long配合__int128中转实现安全模乘即可；超64位才需第三方大整数库或手写模乘。
Miller-Rabin 测试需要自己实现大整数运算吗？
不需要从零写大整数——__int128 在 GCC 下能处理约 39 位十进制数（2^128 ≈ 3.4e38），对大多数竞赛/工程场景已够用；超过则必须用第三方库（如 boost::multiprecision::cpp_int）或手写模乘。别硬刚 std::string 模拟，出错率高、速度慢。
关键判断点：你的“大整数”是否超过 2^64？若输入是 uint64_t 范围内（≤ 18446744073709551615），直接用 unsigned long long + 快速模乘即可；超了就必须引入任意精度整数类型。
如何安全实现模幂运算（mod_pow）避免溢出？
标准 pow(base, exp, mod) 在 C++ 里不存在，手动写时最常见错误是 base * base % mod 直接溢出。必须用“乘法拆解”或编译器内置函数。
- 对
unsigned long long：用__int128中转，例如(__int128)a * b % mod - 若禁用
__int128（如某些 OJ），改用“二进制拆分乘法”（也叫俄罗斯农民乘法）：mul_mod(a, b, mod)逐位累加，每步都取模 - 绝不能写
(a % mod) * (b % mod) % mod—— 乘法本身已溢出，取模无效
示例片段（GCC + __int128）：
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t mod) {
return (__int128)a * b % mod;
}
uint64_t mod_pow(uint64_t base, uint64_t exp, uint64_t mod) {
uint64_t res = 1;
while (exp) {
if (exp & 1) res = mul_mod(res, base, mod);
base = mul_mod(base, base, mod);
exp >>= 1;
}
return res;
}
哪些底数能保证 64 位整数范围内的确定性判定？
对 n ，只需测试固定底数集即可 100% 正确，无需随机化。这是 Miller-Rabin 实际落地的关键——不是“大概率正确”，而是“完全确定”。
根据 J. Grantham 2001 年结果，以下 12 个底数可覆盖全部 uint64_t 范围：
- 但实践中更常用的是 7 个底数：
{2, 325, 9375, 28178, 450775, 9780504, 1795265022} - 若你只处理
n ，仅需 <code>{2, 7, 61}—— 这组更快，且无例外 - 注意：底数必须
，且 <code>n为奇数（偶数直接返回 false，除 2 外）
别用随机底数跑 20 轮——对 64 位数纯属浪费，还可能因随机性漏判（比如选到 n 的倍数）。
为什么 n = 2 和 n 必须单独处理？
Miller-Rabin 算法本身要求 n > 2 且为奇数。不处理边界会导致逻辑崩溃或误判：
-
n == 1→ 合数（但算法里常被当作特例跳过） -
n == 2→ 唯一的偶素数，必须硬编码返回 true -
n % 2 == 0→ 除 2 外全为合数，直接返回 false - 还有
n == 0或负数？按题意通常不考虑，但输入校验建议加assert(n > 0)
漏掉 n == 2 是线上 bug 高发点——尤其当测试用例含小质数时，is_prime(2) 返回 false 就说明底层没兜住。
真正麻烦的从来不是算法逻辑，而是模乘怎么不溢出、底数选哪几组、以及 2 和 1 这种边缘值有没有被 quietly 忽略。写完务必用已知素数（如 1000000007、982451653）和合数（如 1000000009 * 1000000007）交叉验证。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
