对 uint64_t 范围内大整数，Miller-Rabin 可确定性判素——需选对基底、用防溢出模乘（如 __int128 或俄罗斯农民法）、正确分解 n−1=d×2^r（用位运算循环右移），避免 pow 溢出与除法误差。
对 uint64_t 范围内的大整数（≤ 2⁶⁴−1），用 Miller-Rabin 判断“是否通过强伪素数测试”不是概率问题，而是确定性问题——只要基底选对、模乘防溢出、边界拦全，结果就是 100% 可靠的。
为什么不能直接用 pow(a, d) % n
因为 a、d、n 都可能接近 2⁶⁴，pow(a, d) 会指数级爆炸，根本存不下。标准库 std::pow 是浮点函数，对整数精度完全不可信；哪怕手写快速幂，中间乘法 result * base 也会溢出 unsigned long long。
- 错误写法：
result = (result * base) % mod—— 乘法一步就溢出，结果全错 - 正确做法：必须用防溢出模乘，如
mul_mod(result, base, mod) - 推荐优先用
__int128（GCC/Clang）做乘后取模：它能安全覆盖到 ≈1e38，够用 64 位输入 - 若需跨平台或处理超大整数（>200 位），必须用加法模拟乘法（俄罗斯农民乘法），每次加完立刻
% mod
如何分解 n−1 = d × 2^r 才不出错
这步看着简单，但对大整数容易逻辑翻车。不能用除以 2 直到奇数——除法慢且终止条件易错；也不能假设 n−1 一定可被 2 整除若干次后剩 1（比如 n=9，n−1=8=1×2³，d 是 1，不是 8）。
- 正确流程：令
temp = n - 1，用while ((temp & 1) == 0)判断末位是否为 0 - 每次循环做
temp >>= 1（cpp_int 或 __int128 都支持），r++ - 循环结束时，
d = temp就是奇数部分，r就是 2 的幂次 - 别写成
d = (n-1) / (1ULL —— 除法不必要，还可能因移位超界出 UB
哪些底数能让 64 位整数判定 100% 正确
网上流传的 {2,3,5,7} 或 {2,3} 完全不够。比如 n = 3215031751 就是能骗过这四个底数的合数，会被误判为素数。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 数学上已验证的最小完备集是这 7 个：
{2, 325, 9375, 28178, 450775, 9780504, 1795265022} - 顺序无关，但缺一不可；所有底数都必须先
% n，若结果为 0 则跳过该轮（此时n显然不是素数） - 特别注意：
n == 2必须提前返回true；n 或 <code>n == 4必须提前返回false - 若
n小于某个底数（如n=3时遇到底数 325），直接跳过，不参与测试
最容易被忽略的预处理和早期返回
Miller-Rabin 主循环只处理奇数 n ≥ 3。漏掉边界检查，后面所有计算都失去意义。
- 必须最先处理：
n ；<code>n == 2 → true；n == 4 → false - 紧接着判偶：
(n & 1) == 0 → false（即所有偶数，除了 2） -
n == 1和n == 0不仅不是素数，还会让n−1变成极大正数或 0，导致d×2^r分解失败 - 这些判断总共不到 10 行，但少写一行，函数在
n=1、n=4、n=2047上就会返回错误结果
真正难的从来不是模幂或平方循环，而是把 n == 1、n == 2、n == 4、偶数、底数越界这些点全兜住——它们不常出现，但一旦触发，整个判定链就崩了。
