为什么我的梅森素数代码在指数越大时速度更快？

Question

为了好玩，我正在用 Rust 编写一个程序来检查大数是否是梅森素数。由于某种原因，当我使用指数 1_000_000_000 测试程序时，大约需要 5 秒，但当我使用更小的指数 82,589,933（生成最大的梅森素数）时，它永远不会完成处理。你们有人知道发生了什么事吗？为什么更大的指数会提高代码的性能？

use std::str::FromStr;
use num::{BigInt, One, Zero};

fn is_prime(number: &BigInt) -> bool {
    let mut iteration: BigInt = BigInt::from(2);

    while iteration < *number {
        if number % &iteration == Zero::zero() {
            return false;
        }

        iteration += BigInt::one();
    }

    true
}

fn main() {
    let exponent: u32 = 1_000_000_000; // when changed to 82,589,933 it never finishes
    let number: BigInt = BigInt::from_str("2").unwrap().pow(exponent) - BigInt::one();
    let is_prime: bool = is_prime(&number);
    println!("2^{exponent} - 1 is prime: {}", is_prime);
}

Answer 1

答案很简单：指数越大，你的代码很快就能找到除数，所以它很快就会结束。对于较小的、精心选择的指数，它实际上会尝试每个较小的数字来检查它是否是除数，这不会结束，因为 2^82,589,933 次迭代比任何可想象的时间跨度都要大得多。