7
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ You method is doing way to much. You really should separate the responsibilities into methods. \$\endgroup\$ – Heslacher Jun 1 '16 at 7:07
3
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for your review! I really appreciate the effort you have put into this, for a moment I had even thought that it would never get a review. I have just put a follow-up question up on codereview.stackexchange.com/questions/130101/… though I have to mention that I made this several days ago and that I have not incorporated some of your comments on this post. \$\endgroup\$ – skiwi Jun 4 '16 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.