对64位整数应使用确定性Miller-Rabin（基底{2,3,5,7,11,13,17,19,23,29,31,37}）确保100%正确；对几百位大整数才用随机Miller-Rabin；小整数优先试除法。
对几百位以上的大整数，Miller-Rabin 是唯一实际可用的素性判断方案；对 64 位以内整数，它反而比试除法慢，且引入误判风险。
什么时候该用 Miller-Rabin 而不是 is_prime 循环试除？
关键看输入范围和性能要求：
- 输入是
uint64_t（≤ 2⁶⁴−1 ≈ 1.8×10¹⁹）：优先用确定性基底测试（如{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}），可 100% 正确，单次耗时 - 输入是
__int128或字符串表示的超大整数（如 RSA 密钥生成）：必须用Miller-Rabin，且需配合快速模乘（mul_mod）避免溢出 - 输入是小整数（
n ）：直接试除到 <code>sqrt(n)更快、更安全，无需随机化
误用场景：拿 Miller-Rabin 去判 1000000007 是否为质数——它本就是已知素数，且 sqrt(1e9) ≈ 31623，试除不到 1 万次就完事，而 Miller-Rabin 至少要做 3 轮幂模运算，每轮还要拆指数、做 log₂(n) 次平方，纯属加戏。
Miller-Rabin 的核心三步：分解、幂模、二次探测
以判断 n = 101 为例（n−1 = 100 = 2² × 25，即 s = 2, d = 25）：
立即学习“C++免费学习笔记（深入）”；
- 选一个
a ∈ [2, n−2]，比如a = 3 - 算
x = pow_mod(a, d, n) = 3²⁵ mod 101 = 10—— 若结果是1或n−1（即 100），直接进下一轮 - 否则执行
s−1次二次探测：每次x = (x * x) % n，检查是否出现n−1；若中途得1但上一步不是n−1，则n必为合数（违反二次探测定理）
常见错误：漏掉 n == 2 或 n == 3 的特判，或把 n−1 写成 n 导致模运算错位；还有人用普通乘法做 pow_mod，在 n > 2³² 时直接溢出，结果全错。
64 位整数的确定性基底选择
对 uint64_t 范围内所有整数，只需固定测试以下 12 个底数，即可 100% 判定素性，无需随机：
const uint64_t bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};注意：base[i] >= n 时跳过该轮（比如 n = 3 时不能用 a = 3）；n 是偶数且 ≠2 时直接返回 false；n 直接返回 false。这个列表已被数学证明覆盖全部 64 位合数的“强伪证”（strong pseudoprimes）。
别抄网上随便写的 {2, 3, 5, 7} —— 它只对 n 有效，超过就可能把 <code>3215031751（一个合数）误判为素数。
快速模乘 mul_mod 为什么不能省？
C++ 原生不支持 128 位乘法模运算。当 a 和 b 都接近 2⁶⁴ 时，a * b 必然溢出 uint64_t，导致 pow_mod 计算完全失效。
可靠做法是用 long double 做近似减法（主流竞赛代码常用）：
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
if (m <= 1) return 0;
uint64_t q = (uint64_t)((long double)a * b / m);
int64_t r = (int64_t)(a * b - q * m);
return r < 0 ? r + m : r;
}或者用分治快速乘（O(log b) 时间，更稳但稍慢）。切记：只要用了 Miller-Rabin，就必须配套正确实现的 mul_mod，否则所有结果都不可信。
真正容易被忽略的是：即使你只处理 64 位数，只要中间乘积可能 ≥2⁶⁴，就必须走模乘逻辑——这不是“优化”，而是 correctness 的底线。
