Using Sieve of Eratosthenes, I created a function that returns a vector of primes up to given limit.
fn prime_until(limit: usize) -> Option<Vec<usize>> {
if limit <= 1 {
return None;
}
// limit + 1 because of zero based indexing
let mut nums = vec![true; limit + 1];
nums[0] = false; // zero is not a prime
nums[1] = false;
for i in 0..nums.len() {
if !nums[i] {
continue;
}
let mut j = i * i;
while j <= limit {
nums[j] = false;
// lets say j == i * 2,
// j + i == i * 3
// basically increment the multiplication
j += i;
}
}
Some(
nums.iter()
.enumerate()
.filter(|(_, is_prime)| **is_prime)
.map(|(i, _)| i)
.collect(),
)
}
On my computer, it can produce the primes up to 100,000,000 (5,761,455 primes) in ~1.8s when compiling with cargo build --release
.
$ time ./sieve_of_eratosthenes
[src/main.rs:8] &primes.as_ref().unwrap().len() = 5761455
real 0m1.698s
user 0m1.628s
sys 0m0.067s
Update #1: Using this line seems to speed things up a little bit. Though I heard that there might be some problem with precision etc.
...
nums[0] = false; // zero is not a prime
nums[1] = false;
for i in 0..f32::sqrt(nums.len() as f32) as usize { // here
if !nums[i] {
continue;
}
...
$ time ./sieve_of_eratosthenes
[src/main.rs:8] &primes.as_ref().unwrap().len() = 5761455
real 0m1.554s
user 0m1.504s
sys 0m0.048s
Are my implementation good? What can be improved?