Rust梅森素数检测代码：为何更大指数运行更快？

你的问题核心在于暴力试除法完全不适合大数素性检测，再加上两个指数的特性差异，导致了看似反常的结果：

1. 指数1,000,000,000时快速结束的原因 #

10亿是合数，而且2^1000000000 - 1能被3整除，所以你的试除循环只需要执行到iteration=3就会发现整除，直接返回false，程序瞬间结束。

验证这个结论很简单：

• 2的偶数次幂模3的结果是1（因为2²=4≡1 mod3，所以2^(2k)=(2²)^k≡1^k=1 mod3）
• 10亿是偶数，因此2^1000000000 ≡1 mod3，减1后就是0 mod3，必然能被3整除。

2. 指数82,589,933时卡住的原因 #

82,589,933是一个素数，对应的2^82589933 -1是已知的最大梅森素数。你的暴力试除法要证明它是素数，需要从2开始试除到√(2^82589933 -1)——这个数是一个拥有1200多万位的超大数，试除到这个程度需要的时间远超人类的生命周期，自然永远无法结束。

3. 正确的解决方法：使用卢卡斯-莱默检验法 #

暴力试除法对大数完全无用，检测梅森素数有专门的高效算法：卢卡斯-莱默检验法，它不需要试除，而是通过迭代计算来验证素性，时间复杂度远低于暴力试除。

这里给一个简化的卢卡斯-莱默检验实现示例（针对梅森数2^p -1，p是奇素数）：

use num::{BigInt, One, Zero};

// 卢卡斯-莱默检验：仅适用于p为奇素数的梅森数2^p -1
fn lucas_lehmer(p: u32) -> bool {
    if p == 2 {
        return true;
    }
    let mut s = BigInt::from(4);
    let m = BigInt::from(2).pow(p) - BigInt::one();
    for _ in 0..(p - 2) {
        s = (&s * &s - BigInt::from(2)) % &m;
        if s.is_zero() {
            return true;
        }
    }
    s.is_zero()
}

fn main() {
    let exponent: u32 = 82_589_933;
    // 先验证指数是否为素数（这里简化处理，实际需要先检查p的素性）
    // 注意：实际使用时需要先确保p是素数，否则卢卡斯-莱默检验不适用
    let is_mersenne_prime = lucas_lehmer(exponent);
    println!("2^{exponent} - 1 is prime: {}", is_mersenne_prime);
}

注意：实际使用时，需要先验证指数p本身是素数，因为只有当p是素数时，2^p -1才有可能是素数。

内容的提问来源于stack exchange，提问作者figgyfarts