MillerRabin 比试除法快得多，因其只需固定轮数模幂运算（如12轮，每轮O(log³n)），而试除法最坏需检查至√n（64位数达上亿次）；虽有误判合数概率，但选对7个特定底数可对64位数确定性判断。
为什么 MillerRabin 比试除法快得多？
因为试除法最坏要检查到 √n，对 64 位整数来说可能要跑上亿次；而 MillerRabin 只需固定轮数（比如 12 轮）的模幂运算，每轮复杂度是 O(log³n)，实际运行快两个数量级以上。但它不是绝对准确——小概率把合数判成素数，不过选对底数后，对 64 位内所有数都能做到确定性判断。
__int128 是绕不过去的坎
做 modmul(a, b, mod) 时，a 和 b 都接近 mod（比如 10¹⁸），直接 a * b % mod 必然溢出。Clang/GCC 下可用 __int128 中转：
long long modmul(long long a, long long b, long long mod) {
return (__int128)a * b % mod;
}但注意：MSVC 不支持 __int128，Windows 下得换快速乘（如二分加法），或者改用 unsigned long long + 进位拆分——否则一算就错。
- 没处理溢出时，
modmul返回值随机，MillerRabin判定结果完全不可信 - 即使编译器支持
__int128，也要确认目标平台是 Linux/x86-64；macOS 的 Clang 默认不启用该扩展 - 某些 OJ（如 Codeforces）用的是 GCC+Linux，
__int128安全；但 POJ、HDU 等老环境大概率不支持
底数选 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 就够了
这是目前已知最小的、能对所有 unsigned long long 范围内整数做确定性判定的底数集合（覆盖 2⁶⁴ 内全部数）。别自己乱试 {2, 3, 5, 7} —— 对 32 位数还行，但对 10¹⁸ 级别的数，漏判合数的概率高得离谱。
立即学习“C++免费学习笔记（深入）”；
- 少于 7 个底数 → 可能漏掉像
3186658578340311511这样的强伪素数 - 只用
2单独测试 → 对偶数或小合数快，但对形如2^64 - 59这种数基本失效 - 底数顺序无关性能，但建议从小到大排，方便提前退出
is_prime(n) 必须先特判小因子和边界
别一上来就进 MillerRabin 循环。小于 100 的数用查表或试除更快；负数、0、1、2、3、4 要单独处理；偶数除了 2 全部返回 false。
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
if (n < 100) {
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0) return false;
return true;
}否则每次调用都多跑十几轮模幂，对高频小数（比如筛法里反复查 10⁵ 内的数）完全是浪费。
- 不特判
n == 2→ 所有偶数进主流程，白费一轮modpow - 不筛掉
n % 3 == 0等小因子 → 大量合数本可在 O(1) 内拒绝，却拖进 O(log³n) 流程 - 把
n == 1漏掉 → 直接返回 true，这是经典翻车点
真正难的不是算法本身，是让每个分支都落在它该在的位置——尤其是溢出处理和底数选择，错一点，整个判断就不可靠。
