C++如何进行快速素数判断？（Miller-Rabin算法实现）

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，这是经典翻车点

真正难的不是算法本身，是让每个分支都落在它该在的位置——尤其是溢出处理和底数选择，错一点，整个判断就不可靠。