美利坚强素数只能通过查表或验证已知候选者来判定；需先检查n+1是否为2的幂以确定p，再确认p为素数且n=2^p−1，超出uint64_t范围的数无法直接计算。
美利坚强素数（Mersenne prime）是形如 2^p − 1 的素数，其中 p 本身也必须是素数。直接暴力判断任意整数是否为美利坚强素数，在实践中几乎不可行——因为目前已知的美利坚强素数只有 51 个，最大值超过 282,589,933−1，远超 uint64_t 范围。所以，**你不能对一个任意输入的整数做通用判定；只能对已知候选者（即形如 2^p − 1 且 p 为小素数）做验证，或查表比对**。
如何快速验证一个数是否形如 2^p − 1
这是第一步，也是最廉价的过滤。若输入 n 不满足该形式，直接返回 false。
-
n必须为正整数，且n + 1必须是 2 的幂（即(n + 1) & n == 0且n > 0） - 求出
p = log2(n + 1)，需确保p是整数且 ≥ 2（因为2^2 − 1 = 3是最小美利坚强素数） - C++ 中可用
std::bit_width(static_cast<unsigned long>(n + 1)) - 1</unsigned>得到精确的p（C++20），或用__builtin_clzll配合位运算避免浮点误差 - 注意：
log2函数易因精度丢失误判大数（如n = (1LL 时，<code>round(log2(n+1))可能仍得 60，但浮点误差可能让pow(2, p) != n + 1）
如何验证 p 是否为素数
一旦得到 p，必须确认它本身是素数。这是必要条件——例如 2^11 − 1 = 2047 = 23 × 89，虽形如 2^p − 1，但 p = 11 是素数，而 2047 不是素数；反例是 p = 11 合法，但 p = 4（非素数）直接排除。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 若
p ，用试除法（<code>i ）足够快且无依赖 - 若
p较大（如 > 10⁵），建议用 Miller-Rabin 检测（单次误判率 - 不要用
std::sqrt(p)做上界——改用i * i 避免浮点舍入问题 - 特别注意：
p = 2, 3, 5, 7, 13, 17, 19, 31, ...这些才是合法指数；p = 1或p = 0不允许（2^1 − 1 = 1非素数）
如何验证 2^p − 1 是否为素数（Lucas-Lehmer 检验）
这是唯一被数学证明适用于美利坚强素数的高效判定法，但**仅适用于 p 为奇素数的情形**（p = 2 单独处理）。它不适用于普通整数，也不能用在非 2^p − 1 形式上。
立即学习“C++免费学习笔记（深入）”；
- 定义序列：
s₀ = 4，sᵢ₊₁ = (sᵢ² − 2) mod M_p，其中M_p = 2^p − 1 -
M_p是素数 ⇔s_{p−2} ≡ 0 (mod M_p) - 关键难点：
sᵢ增长极快，必须全程模M_p运算；而M_p可能远超uint64_t（如p > 64），需用大整数库（如boost::multiprecision::cpp_int）或手写模平方优化 - 标准实现中，
s² mod M_p可用“减法优化”避免完整乘法：因M_p是二进制全 1 数，可用位拆分加速（但 C++ 标准库无内置支持） - 别尝试对
p > 100手写 LL 测试——已知p = 82589933的检验耗时数周，靠分布式计算完成
真正实用的做法是：对输入 n 先检查是否为已知美利坚强素数之一。截至 2024 年，全部 51 个都小于 282,589,933，但只有前几个（p ≤ 61）对应的 M_p 能放进 uint64_t。超出范围的数，C++ 程序无法直接存储或运算，更谈不上判定——这时候不是算法问题，是数据表示的硬限制。
