The rusty Sieve of Eratosthenes

Question

To get familiar with the Rust language I've decided to implement the method of Sieve of Eratosthenes to find primes up to a number N.

I have created the following code that both prints the prime number and whether it is prime in tabular format and prints a vector consisting of the prime numbers.

As additional library I'm using the external library bit-vec.

extern crate bit_vec;

const MAXIMUM_PRIME: u32 = 1000;

use bit_vec::BitVec;

fn main() {
    let mut prime_bit_vector = BitVec::from_elem((MAXIMUM_PRIME + 1) as usize, true);
    let sqrt_prime = ((MAXIMUM_PRIME as f64).sqrt() as u32) + 1;

    for i in 2..(sqrt_prime+1) {
        if prime_bit_vector[i as usize] {
            let mut j = i * i;
            while j <= MAXIMUM_PRIME {
                prime_bit_vector.set(j as usize, false);
                j += i;
            }
        }
    }

    let maximum_prime_length = MAXIMUM_PRIME.to_string().len();
    for i in 0..(MAXIMUM_PRIME+1) {
        println!("{index:<width$} {is_prime}", index = i, is_prime = prime_bit_vector[i as usize], width = maximum_prime_length as usize);
    }

    let primes: Vec<_> = prime_bit_vector.iter().enumerate().filter(|t| t.1).map(|t| t.0).collect();
    println!("Primes: {:?}", primes);
}

Answer 1

To start, let me heartily compliment you on your code! You have clearly put effort into learning what idiomatic Rust code looks like. Spacing of operators seems to be accurate, and using code like Vec<_> is top-notch.

I actually took a long time to write a review because there didn't seem to be much to say! After a bit, there were some small things:

1. I agree that your code could be improved by splitting out some functions:

   1. Separates the concerns of building the primes and printing them.
   2. Allows parameterizing the maximum easier.
   3. Cordons off the mutability of the BitVec to a smaller scope.
   4. Gives names to what is being printed.

2. Instead of passing the maximum prime when printing, it can be based on the size of the BitVec. It's a little odd as you have to subtract one, so maybe you might want to create a type for the primes that abstracts that away...

3. Generally, I'd recommend avoiding array indexing due to performance concerns — indexing has slight overhead due to bounds checking. I'm not sure if that applies for a BitVec though. I still like the enumerate solution better.

4. From previous Sieves, I think that you may want to write ((MAXIMUM_PRIME as f64).sqrt() as u32) + 1 as (MAXIMUM_PRIME as f64).sqrt().ceil() as u32. I think that's more correct in more cases, and probably communicates intent better.

extern crate bit_vec;

const MAXIMUM_PRIME: u32 = 1000;

use bit_vec::BitVec;

fn primes_up_to(max: u32) -> BitVec {
    let mut prime_bit_vector = BitVec::from_elem((max + 1) as usize, true);
    let sqrt_prime = ((max as f64).sqrt() as u32) + 1;

    for i in 2..(sqrt_prime+1) {
        if prime_bit_vector[i as usize] {
            let mut j = i * i;
            while j <= max {
                prime_bit_vector.set(j as usize, false);
                j += i;
            }
        }
    }

    prime_bit_vector
}

fn print_table(prime_bit_vector: &BitVec) {
    let max = prime_bit_vector.len() - 1;
    let maximum_prime_length = max.to_string().len();

    for (i, is_prime) in prime_bit_vector.iter().enumerate() {
        println!("{index:<width$} {is_prime}", index = i, is_prime = is_prime, width = maximum_prime_length);
    }
}

fn print_primes(prime_bit_vector: &BitVec) {
    let primes: Vec<_> = prime_bit_vector.iter().enumerate().filter(|t| t.1).map(|t| t.0).collect();
    println!("Primes: {:?}", primes);
}

fn main() {
    let prime_bit_vector = primes_up_to(MAXIMUM_PRIME);
    print_table(&prime_bit_vector);
    print_primes(&prime_bit_vector);
}

---

In the future, two Rust enhancements will help the code look even better:

1. Someday we will have inclusive ranges, which would transform x..(y+1) into some nicer syntax (perhaps x...y?).

2. Someday the step_by range iterator adapter will exist, which would transform the j += i to something like ((i*i)...MAXIMUM).step_by(i)