“美利坚强素数”实为Miller–Rabin素性测试的戏称，是一种概率性素数判定算法；对64位整数，用7个固定底数可实现100%确定性判定，但需__uint128_t防溢出、特判小数及边界条件。
什么是美利坚强素数（Miller–Rabin素数判定）
“美利坚强素数”是中文网络对 Miller–Rabin 素性测试的戏称，它不是一种特殊素数，而是一种**概率性素数判定算法**。C++ 标准库不提供现成函数，必须手动实现或调用第三方库（如 GMP），但实际项目中常需手写轻量版用于竞赛、密码学预筛或大数快速判断。
为什么不能直接用 sqrt(n) 试除法
对大于 10^12 的整数，试除到 sqrt(n) 在 C++ 中可能超时或溢出（sqrt 对 long long 不精确，且循环次数达百万级）。而 Miller–Rabin 平均时间复杂度为 O(k log³n)（k 是测试轮数），对 64 位整数 只需 12 轮即可确定性判别（见下文）。
-
int或long long范围内，试除法只适用于n < 10^10左右 -
sqrt(n)计算本身在double下对n > 2^53会丢失精度，导致循环边界错误 - 试除法无法处理形如
n = 999999999999999989（真实大素数）的快速验证需求
64 位整数下确定性 Miller–Rabin 的正确写法
对 unsigned long long（0 到 2⁶⁴−1），只需用固定底数集 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 测试，即可 100% 正确判定——这是由 J. Jaeschke 和 S. Zhang 等人验证过的最小完备集合。
关键实操点：
立即学习“C++免费学习笔记（深入）”；
- 必须用
__uint128_t（GCC/Clang 支持）或自写模乘避免a * b % n中间结果溢出；否则mulmod(a, b, n)会因a*b > 2^64而截断 - 先特判小素数：
n < 2→ false，n == 2→ true，n % 2 == 0→ false - 将
n−1拆为d * 2^r时，用while ((d & 1) == 0)循环右移，而非除法（避免无符号除零风险） - 对每个底数
a，计算powmod(a, d, n)，再反复平方检查是否出现1前的非平凡根n−1
示例核心片段（无完整模板）：
bool miller_rabin(unsigned long long n) {
if (n < 2) return false;
if (n == 2) return true;
if ((n & 1) == 0) return false;
unsigned long long d = n - 1;
int r = 0;
while ((d & 1) == 0) d >>= 1, r++;
constexpr unsigned long long bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
for (unsigned long long a : bases) {
if (a % n == 0) continue; // a ≥ n 时跳过（实际不会发生，但防误）
unsigned long long x = powmod(a, d, n);
if (x == 1 || x == n-1) continue;
bool comp = true;
for (int i = 1; i < r; i++) {
x = mulmod(x, x, n);
if (x == n-1) { comp = false; break; }
}
if (comp) return false;
}
return true;
}
容易被忽略的底层陷阱
很多人抄了代码却在 n = 2^63−1（即 9223372036854775807）上返回 false，原因不是算法错，而是实现细节崩了：
-
mulmod若用((a % mod) * (b % mod)) % mod，对a,b ≈ 2^64仍会溢出——必须用__uint128_t或二分乘法 -
powmod的快速幂若未处理base == 0或exp == 0边界，可能返回 1 误判合数为素数 - 底数数组若漏掉
1795265022，对n = 3186658578340311511这类强伪素数会判错 - 输入为
1或0时未前置检查，导致n−1变成全 1 位宽的负数（无符号下是极大值），后续逻辑全乱
真正可靠的实现，往往比看起来多 10 行防御性代码，少一行都可能在某个特定大数上翻车。
