Calculating Prime Numbers with Rust

· 2min · Dan F.

I know it's a simple program, but a few months ago I wrote a little python script to find prime numbers. The little python script was able to find all the prime numbers up to 10,000,000 in 2:40 minutes. I wonder if rust can beat that?

Luckily, I knew that the python script was able to accurately find primes, as the count found under 10 million should be 664,579, which is also what my script found.

Since I already had the algorithm, all that was needed was to port the code over to rust.

This is the code I ended up with:

fn main() {

    let mut found: i64 = 0;                                     // Set found count to 0

    for count in 1i64..10_000_000 {                             // Count integers from zero to ten million
        if count % 2 != 0 {                                     // Continue if count is not even
            if check_prime(&count) {                            // Check if odd number if prime, using check_prime
                found = add(found,1);                           // Increment found count
                println!("{},{}",&count,&found);                // Print number, and total found
            }
        }
    }

    fn check_prime(count: &i64) -> bool {                       // Function receives int, and returns bool
        let mut stop = ((*count as f64).sqrt() + 1.0) as i64;   // Find stopping number to loop to
        for i in 3..stop {                                      // Start at 3 and go until stop
            if i % 2 != 0 {                                     // Continue if i is not even
                if count % i == 0 {                             // If count is divisible by i;
                    return false                                // Return false
                }
            }
        }
        return true                                             // Only return true if never returned false
    }

    fn add(number: i64, add: i64) -> i64 {                      // Function adds a number to a number
        number + add                                            // Return number plus number
    }
}

To compile it yourself, simply run cargo new --bin prime, and copy this code over to prime/src/main.rs, and compile with cargo build --release.

With this binary, I was able to find all primes up to 10 million in a little over eleven seconds! What a difference.

[admin@openbox rust/prime]# time ./target/release/prime
1,1
3,2
5,3
7,4
11,5

...

9999937,664575
9999943,664576
9999971,664577
9999973,664578
9999991,664579

real    0m11.116s
user    0m6.850s
sys     0m0.940s

Has been tested on OpenBSD 6.5-current