Calculating Prime Numbers with Rust
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