直接试除法对超10^12整数超时；miller-rabin用7个特定底数在uint64_t范围内可确定性判质，关键需安全模乘防溢出并严格预处理边界情况。
为什么不能直接试除法判断大整数是否为质数
当数字超过 10^12，试除到 sqrt(n) 会超时；而像 9824516539 这类 10 位质数，试除需要约 10^5 次运算，在高频调用或竞赛限时场景下不可靠。Miller-Rabin 是概率性算法，但对 64 位整数，选好底数后可做到确定性判别——它不“猜”，而是数学上能覆盖所有反例。
如何用 uint64_t 安全实现 Miller-Rabin
核心陷阱是乘法溢出：a * b % n 中 a 和 b 都接近 2^64，直接乘必溢出。必须用模乘（modular multiplication）避免。
- 先写一个安全的
mul_mod(a, b, mod)：用类似快速幂的加法倍增，每次加法前检查是否会溢出（或用__int128如果编译器支持） - 再写
pow_mod(base, exp, mod)，内部调用mul_mod - 主逻辑中，把
n-1拆成d * 2^r，对每个测试底数a计算pow_mod(a, d, n)，再反复平方检查是否出现非平凡根
示例片段（关键分支）：
if (n <h3>哪些底数能让 <code>uint64_t</code> 范围内 100% 准确</h3><p>不是随便选几个小质数就行。对 <code>64</code> 位无符号整数（<code>n ），已知最小完备集合是：<code>{2, 325, 9375, 28178, 450775, 9780504, 1795265022}</code>。用这 7 个数，Miller-Rabin 对所有 <code>n 都是确定性算法。</code></code></p>
- 如果只用
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}，仍可能漏判某些强伪素数（如318665857834031151167461） - 实际工程中可先特判小质数（
），再对大数用上述 7 数集合 - 注意：底数必须小于
n，否则pow_mod会出错或退化
常见误判现象和调试线索
返回 true 但实际是合数？大概率出在模乘或模幂环节。
-
mul_mod返回 0 但输入非零 → 溢出未检测，或__int128被禁用且 fallback 逻辑有 bug - 对
n = 4或n = 1没做前置过滤 → 直接进 Miller-Rabin 主循环，导致n-1 = 3拆解异常 - 测试底数数组里混入了
>= n的值（比如n=3时用了325）→pow_mod(325, d, 3)实际算的是pow_mod(1, d, 3)，失去区分度 - 没处理
n是偶数的快速出口，导致对2^63这类大偶数也跑完整流程，浪费时间且易触发边界错误
真正难的不是原理，是让每一步模运算在 uint64_t 下不溢出、不降级、不越界。写完务必用已知强伪素数（如 2047, 1373653, 25326001）和对应质数交叉验证。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
