我正在用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);
}

推荐答案

答案很简单:使用较大的指数,你的代码很快找到一个除数,所以它很快结束(实际上,2^1_000_000_000-1 = (2^2-1)(2^499_999_999+...+1) = 3n,其中n是一个很大的数字,所以它花了五秒钟进行两次迭代).使用较小的、精心 Select 的指数,它实际上try 每一个较小的数字来判断它是否是一个除数,这不会结束,因为2^82,589,933次迭代比任何可以想象的时间跨度都要大得多.

Rust相关问答推荐

如何在Rust中为具有多个数据持有者的enum变体编写文档 comments ?

关于Rust 中回归的逻辑

展开枚举变量并返回所属值或引用

具有对同一类型的另一个实例的可变引用的

为什么Rust函数的移植速度比C++慢2倍?

integer cast as pointer是什么意思

字段类型为Boxed的 struct 的生存期必须超过static

如何使用RefCell::JOYMOMTborrow 对 struct 不同字段的可变引用

我如何使用AWS SDK for Rust获取我承担的角色的凭据?

为什么&;mut buf[0..buf.len()]会触发一个可变/不可变的borrow 错误?

仅发布工作区的二进制 crate

Rust Option 的空显式泛型参数

如何以与平台无关的方式将OsString转换为utf-8编码的字符串?

通过mem::transmute将数组展平安全吗?

decltype、dyn、impl traits,重构时如何声明函数的返回类型

如何从 rust 中的同一父目录导入文件

以 `static` 为前缀的闭包是什么意思?我什么时候使用它?

改变不实现克隆的 dioxus UseState struct

如何将 while 循环内的用户输入添加到 Rust 中的向量?

相互调用的递归异步函数:检测到循环