May someone take a quick look on my code?

Hey lovely Rust community,
I am starting to learn Rust and one of my first programs I write in every language I try to learn is a prim finder(sieve of Eratosthenes) because it always leave some room for improvements and tweaks, even being quite simple in terms of complexity.
I am thankful for every critique you might give me.

 use std::io::{stdin, stdout, Write};

//read user input and returns it as String
fn read() -> usize {
    let mut input = String::new();
    stdout().flush()
        .expect("failed to flush");
    stdin().read_line(&mut input)
        .expect("failed to read");
    return input.trim().parse().unwrap();

}

struct BoolList {
    table :Vec<bool>
}

impl BoolList {
    fn new() -> Self {
        BoolList {
            table: Vec::new()
        }
    }

    //fill the list with true values (assuming each number is prim in the beginning)
    fn fill_vec(&mut self, int: usize) {
        for _i in 0..int {
            self.table.push(true);
        }
    }

    //set the position to false
    fn set_false(&mut self, pos :usize) {
        self.table[pos] = false;
    }

    //set all multiples of val to false
    fn iter_value(&mut self, value :usize) {
        let mut coof :usize = 2;

        if self.table[value] == true { 
            while value * coof < self.table.len() {
                self.set_false(value * coof);
                coof += 1;
            }
        }
    }
}
//iterate over each value in the list and change multiples to false
fn iter_list(list :&mut BoolList) {
    for num in 2..list.table.len() {
       list.iter_value(num); 
    }
}

fn pretty_print(list :&BoolList) {
    for num in 2..list.table.len() {
        if list.table.get(num) == Some(&true)  {
            println!("prim: {}",num);
        }
    }
}

pub fn main() {
    let mut prim_list = BoolList::new();
    
    println!("what should be the prim bound?");
    //fills empty prim list assuming that every number is prim at start 
    //with users input as upper bound
    prim_list.fill_vec(read());
    //unvalue all numbers which aren't prim
    iter_list(&mut prim_list);
    //print list
    pretty_print(&prim_list);
}

First thing I would change is to start writing your expect messages with the thing you actually expect. Instead of .expect("failed to flush"), you should write .expect("flush stdout"). If you do this, the error you get is thread 'main' panicked at 'flush stdout'.

You can also add more details than that .expect("flush stdout to prepare reading user input") and it will look much more useful and function as a nice comment.

Next, Vec<bool> is probably not very space efficient, and I would look at using something like BitVec instead.

Reading the code, it's not clear to me how much benefit there is from having the separate methods. E.g. fill_vec doesn't quite do what I would expect it to (if called when table is not empty, it will append trues to the end of existing data), and so I would find it clearer to see all the logic for building the sieve in one place.

(basically, I try to avoid designs where a type has a bunch of methods that the users need to call in a specific order for the type to be useful)

fn get_sieve(len: usize) -> Vec<bool> {
    // fills empty prim list assuming that every number is prim at start 
    let mut table = vec![true; len];

    // unvalue all numbers which aren't prim
    for num in 2..table.len() {
        let mut coof :usize = 2;

        if table[value] == true { 
            while num * coof < table.len() {
                table[num * coof] = false;
                coof += 1;
            }
        }
    }
    table
}

You can iterate over the multiples of a number more cleanly using step_by.

for multiple in (2*num..table.len()).step_by(num) {
    table[multiple] = false;
}

An optimization: By the time you reach a given value for num, you've already crossed off every multiple that is less than num*num:

for multiple in (num*num..table.len()).step_by(num) {
    table[multiple] = false;
}

The .get(num) in pretty_print doesn't make sense because you're only using indices in the range 2..len, so it should never fail. You can use list.table[num].

Try running cargo fmt, as the code has lots of odd formatting choices. (e.g. the Rust community almost universally prefers name: Type over name :Type).

The English spelling is "prime," not "prim."

if x == true is kind of weird when it could just be written as if x. Since if table[num] { sounds ambiguous, I might advise renaming table to is_prime. (so that we have if is_prime[num] {)


I feel like there isn't really a solid convention here, and either way of doing things is equally valid. The same argument about panicked at 'flush stdout' could be applied to panic!() itself, where the convention is pretty clearly to write error messages.

An improvement on @ExpHP's implementation:

fn get_sieve(len: usize) -> Vec<bool> {
    // fills empty prime list assuming that every number is prim at start 
    let mut is_prime = vec![true; len];

    let log_2 = (len as f32).log(2.0).ceil() as usize;
    // unvalue all numbers which aren't prime
    for num in 2..log_2 {
        for not_prime in is_prime.iter_mut().skip(2*num-1).step_by(num) {
            *not_prime = false
        }
    }
    is_prime
}

Three changes:

  • iterate over the vector using an iterator. This cuts down on checking the index on each iteration. Remember indexing is just vec.get(i).unwrap().
  • I only think the outer loop has to go up to the log2 of the length. Might be wrong.
  • I just assign false without checking that it is true. I believe this is faster because you access the memory once, rather than twice in the true case.

Edit: Point 2 and 3 are incorrect. Also it was supposed to be 2*num not 2*num-1.

You have to go up to the square root, not the binary logarithm. playground

Additionally by eliminating the if check, your algorithm becomes much slower, because now you perform the entire inner loop a lot more times than necessary.

I knew that It wasn't quite right.

Oh yeah. I wasn't thinking correctly. I was only considering num being prime, but it could be none prime.

Ok fixed it. playground

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.