梅森素数是形如 $2^p - 1$ 的素数，其中指数 $p$ 本身也必须是素数；它由17世纪法国数学家马林·梅森命名，与完全数一一对应，截至2024年10月已发现52个，最大者超4100万位。
什么是梅森素数？先确认输入是否满足基本形式
梅森素数必须是形如 2^p - 1 的素数，且指数 p 本身也必须是素数。所以第一步不是直接试除，而是检查输入 n 是否能写成 2^p - 1 的形式。
实操建议：
- 对给定正整数
n，先计算n + 1，再判断它是否为 2 的整数次幂：可用(n + 1) & n == 0（前提是n > 0），这是位运算快速判幂方法 - 若成立，用
log2(n + 1)或逐次右移计数得到p；注意log2返回浮点数，需四舍五入后验证pow(2, p) == n + 1 - 若
p≤ 2，直接判：只有p = 2得2^2 - 1 = 3是梅森素数；p = 3 → 7、p = 5 → 31等才可能成立 - 若
n不满足n + 1是 2 的幂，直接返回 false —— 它根本不是梅森数，更不可能是梅森素数
如何高效验证 p 是否为素数？避免误判小合数
因为 2^p - 1 是梅森素数的前提是 p 必须为素数，而 p 本身可能不小（比如 p = 61 对应 2^61 - 1），但通常我们处理的 n 在 uint64_t 范围内，对应 p ≤ 64，所以 p 最大也就 61（因为 2^64 - 1 超出 uint64_t 表示范围）。
实操建议：
- 对
p ≤ 64，可硬编码素数表：{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}，查表比试除更快更稳 - 若想通用，写一个简单试除函数：只需试到
sqrt(p)，且跳过偶数（除 2 外） - 别用
sqrt(p)直接比较浮点数，改用i * i 避免精度问题 - 常见错误：把
p = 11当作合数（因 11 是素数），或漏掉p = 2—— 它合法且关键
验证 2^p - 1 是否为素数：用 Miller-Rabin 还是试除？
当 p 较大（比如 ≥ 17），2^p - 1 可能高达 10 万位以上，此时无法用普通试除。但注意：你在 C++ 中实际能存下的 n 通常是 unsigned long long（64 位），最大支持 p = 64，对应 2^64 - 1 ≈ 1.8e19 —— 这个量级仍可用确定性 Miller-Rabin 或优化试除。
实操建议：
- 对
n ≤ 2^64 - 1，可用已知的 12 个底数集合做确定性 Miller-Rabin（如{2, 325, 9375, 28178, 450775, 9780504, 1795265022}），覆盖全部 64 位整数 - 若嫌 Miller-Rabin 实现复杂，且
n ，可用试除法：只试到 <code>sqrt(n)，步长为 2 和 6k±1，配合预筛小素数（如 2,3,5,7）能快不少 - 别用
sqrt(n)计算上界——对大整数会溢出或失精；改用i 判断循环条件 - 注意：
2^31 - 1 = 2147483647是 int 范围内最大梅森素数，但2^61 - 1已超 int，务必用uint64_t存储和运算
完整流程中容易被忽略的边界与性能陷阱
写完函数跑测试时，常在 n = 3、n = 4、n = 7、n = 8 上出错，根源不在算法逻辑，而在类型转换和边界处理。
实操建议：
-
n = 1：1 + 1 = 2是 2 的幂，p = 1，但 1 不是素数 → 不是梅森素数；必须显式排除p = 1 - 计算
2^p时用1ULL （而非 <code>pow(2, p)），避免 double 精度丢失；但注意p ≥ 64会左移溢出，需提前检查 - 当
p = 64，1ULL 是未定义行为（左移位数等于位宽），应限定 <code>p （因为 <code>2^64 - 1是最大 uint64_t 值） - 不要在每次调用都重复生成素数表或 Miller-Rabin 底数表；静态初始化一次即可
真正麻烦的是 p 本身不大，但 2^p - 1 极大——这时你得决定是否支持大整数。标准 C++ 没内置，靠 __int128（GCC 扩展）最多撑到 p ≈ 127；再往上就得用 GMP 或自己实现模幂，那已经超出“判断一个正整数”的原始场景了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
