-3

I am doing some problems on Project Euler. This challenge requires filtering prime numbers from an array. I was halfway near my solution when I found out that Rust was a bit slow. I added a progressbar to check the progress.

Here is the code: extern 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));
}

I am calling the solve function from my main.rs file. Turns out that the number of iterations in my for loop is a lot faster in the beginning and a lot slower later. 

➜  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

I am sort of drawing a blank in what might be causing this slowdown. It feels like Rust should be able to be much faster than what I am currently seeing. Note that I am telling Cargo to build with the --release flag. I am aware that not doing this might slow things down even further.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
cantdutchthis
  • 31,949
  • 17
  • 74
  • 114
  • 1
    What are you comparing this with? That algorithm is quite inefficient, so it will never beat, say, the Sieve of Eratosthenes, even in an interpreted language. – E_net4 Dec 23 '18 at 16:17
  • 2
    It gets slower as it goes along because you are calling `is_prime` (which has O(n) complexity) with higher and higher inputs. – Peter Hall Dec 23 '18 at 16:17
  • 1
    Imho, you can not get it faster with this is_prime algorithm. Maybe you can look for better prime number checking algorithm or consider an external crate for this purpose – Akiner Alkan Dec 23 '18 at 16:40

1 Answers1

1

The function which is slowing the execution is:

is_prime(i: i32)

You may consider to use more efficient crate like primes or you can check efficient prime number checking algorithms here

Akiner Alkan
  • 6,145
  • 3
  • 32
  • 68
  • 2
    I don't think there exist a know algorithm that could be called "efficient" for searching prime number, also this is a good thing because that would be the end of internet ;) – Stargateur Dec 23 '18 at 17:51
  • Haha you are right, but at least we can find a better solution then O(n) right :) – Akiner Alkan Dec 23 '18 at 19:24