Basic Sieve of Erosthenes

Question

This is a basic command line program that, given a number, returns a list of primes up to and including that number. Also handles a lack of command line arguments and non-number arguments.

I ran into a bunch of problems with Options while I was writing this, which led to me using unwrap() out of desperation. I'd rather never use unwrap, and instead handle None or Err or whatever. Additionally, I'd prefer not to have everything so mutable.

// A bad implementation of the Sieve of Eratosthenes

// Usage: 
//  primesTo x = comma-separated list of all primes up to x

use std::env;

// Returns a vector of primes from 2 to max
fn primes_to(max: u32) -> Vec<u32> {
    let mut all: Vec<u32> = (2..max+1).collect();
    let mut primes: Vec<u32> = vec!();

    while all.len() > 0 {
        let (a, b) = sieve(all, primes);
        all = a;
        primes = b;
    }
    primes
}

// Sieve a non-empty list
fn sieve(list: Vec<u32>, mut primes: Vec<u32>) -> (Vec<u32>, Vec<u32>) {
    // We have a Vec<u32>
    // We want a u32 and a Vec<u32>
    let mut i_list = list.into_iter();
    let head: u32 = i_list.next().unwrap();
    let mut tail: Vec<u32> = i_list.collect();
    tail.retain(|&x| x % head != 0);
    primes.push(head);
    (tail, primes)
}

fn prettyprint_primes(mut primes: Vec<u32>) -> () {
    let temp = primes.pop().unwrap();
    for prime in primes {
        print!("{:}, ", prime);
    }
    print!("{:}", temp);
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let arg: Option<&String> = args.get(1);

    match arg {
        None => {
            println!("Please enter a number to receive primes.");
            println!("Usage:");
            println!("\ttoPrime x");
        },
        Some(x) => {
            match x.parse::<u32>() {
                Ok(max) => {
                    let primes: Vec<u32> = primes_to(max);
                    prettyprint_primes(primes);
                },
                _ => println!("That's not a number; please enter a number"),
            }
        }
    }
}

Answer 1

I think this is one of the few "Sieves of Erosthenes" that actually implements the sieving method; congratulations! ^_^

1. Run rustfmt:

   • Spaces go around binary operators:

     let mut all: Vec<u32> = (2..max + 1).collect();
     

   • vec! should always be called with square brackets:

     let mut primes: Vec<u32> = vec![];
     

   • There's no comma after the curly brace of a match arm.

2. Run Clippy:

   warning: length comparison to zero
     --> src/main.rs:13:11
      |
   13 |     while all.len() > 0 {
      |           ^^^^^^^^^^^^^ help: using `is_empty` is more concise: `!all.is_empty()`
      |
      = note: #[warn(len_zero)] on by default
      = help: for further information visit https://github.com/Manishearth/rust-clippy/wiki#len_zero
   

3. You are declaring types way more frequently than you need to. Type inference can handle most of these cases. Other times, you can let the compiler infer a part of the type, such as with collect: let foo: Vec<_> = iter.collect().

4. Converting a Vec to an iterator, popping one element, then converting back to a Vec is expensive. Instead, just get the first element of the input using the index operator (foo[0]).

5. Once you've done that, you might as well just pass in a mutable reference to the list to avoid taking ownership of the list and passing back ownership and dealing with the tuple output.

6. Once you've done that, there's no reason to pass in the whole prime list just to append to it and get it back. Instead, return the new prime number from the function and append it later.

7. Use your function comments to enhance your function names, instead of them being dead text warning about how to call them ("non empty list").

8. Your desire to avoid unwrap is well-founded. Your code crashes if run with 1 as the argument. To properly format a comma-separated list, check out What's an idiomatic way to print an iterator separated by spaces in Rust? and In Rust, what is the best way to print something between each value in a container. TL;DR: use Itertools::format.

9. Using {:} as the format specifier is very unusual — I had to think hard about what it even meant. You should use just {}.

10. Don't take a Vec if you are just going to iterate over it.

11. Don't explicitly mark () as the return type of a function, that's the default.

12. Instead of collecting your arguments into a vector, just grab the single argument you care about using Iterator::nth.

extern crate itertools;

use itertools::Itertools;

use std::env;

fn primes_to(max: u32) -> Vec<u32> {
    let mut all: Vec<_> = (2..max + 1).collect();
    let mut primes = vec![];

    while !all.is_empty() {
        primes.push(sieve_non_empty_list(&mut all));
    }

    primes
}

fn sieve_non_empty_list(list: &mut Vec<u32>) -> u32 {
    let head = list[0];
    list.retain(|&x| x % head != 0);
    head
}

fn prettyprint_primes(primes: &[u32]) {
    print!("{}", primes.iter().format(", "))
}

fn main() {
    let arg = env::args().nth(1);

    match arg {
        None => {
            println!("Please enter a number to receive primes.");
            println!("Usage:");
            println!("\ttoPrime x");
        }
        Some(x) => {
            match x.parse() {
                Ok(max) => {
                    let primes = primes_to(max);
                    prettyprint_primes(&primes);
                }
                _ => println!("That's not a number; please enter a number"),
            }
        }
    }
}

I'd probably implement the sieve as an iterator, however. This has the effect of removing the need to store the primes (the caller can do so if needed), allowing the caller to get the next prime back quicker, and encapsulates the state of the list so we don't need to document that you can only call functions in certain states.

struct Sieve {
    list: Vec<u32>,
}

impl Sieve {
    fn new(up_to: u32) -> Self {
        Self {
            list: (2..up_to + 1).collect(),
        }
    }
}

impl Iterator for Sieve {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        let val = self.list.get(0).cloned();

        if let Some(head) = val {
            self.list.retain(|&x| x % head != 0);
        }

        val
    }
}

And it can be printed directly as:

let primes = Sieve::new(max);
print!("{}", primes.format(", "))