performance - 我过滤质数的代码的哪一部分导致它在处理时变慢？

Question

我在 Project Euler 上做一些问题.这个挑战需要从数组中过滤质数。当我发现 Rust 有点慢时，我已经接近我的解决方案了。我添加了一个 progressbar查看进度。

代码如下: 外部 crate pbr;

use self::pbr::ProgressBar;

pub fn is_prime(i: i32) -> bool {
    for d in 2..i {
        if i % d == 0 {
            return false;
        }
    }
    true
}

pub fn calc_sum_loop(max_num: i32) -> i32 {
    let mut pb = ProgressBar::new(max_num as u64);
    pb.format("[=>_]");
    let mut sum_primes = 0;
    for i in 1..max_num {
        if is_prime(i) {
            sum_primes += i;
        }
        pb.inc();
    }
    sum_primes
}

pub fn solve() {
    println!("About to calculate sum of primes in the first 20000");
    println!("When using a forloop {:?}", calc_sum_loop(400000));
}

我正在从我的 main.rs 文件中调用 solve 函数。事实证明，我的 for 循环中的迭代次数在开始时要快得多，而在后面要慢得多。

➜  euler-rust git:(master) ✗ cargo run --release
    Finished release [optimized] target(s) in 0.05s
     Running `target/release/euler-rust`
About to calculate sum of primes..
118661 / 400000 [===========>__________________________] 29.67 % 48780.25/s 6s
... 
...
400000 / 400000 [=======================================]     100.00 % 23725.24/s

我有点想不通是什么导致了这种放缓。感觉 Rust 应该能够比我目前看到的快得多。请注意，我告诉 Cargo 使用 --release 标志进行构建。我知道不这样做可能会进一步减慢速度。

Answer 1

减慢执行速度的函数是:

is_prime(i: i32) 

您可以考虑使用更高效的箱子，例如 primes或者您可以检查有效的素数检查算法 here