# Prime Sieve in Rust (Sieve of Eratosthenes)

I am learning Rust and I decided to make a prime sieve program. It works and has comparable performance to my equivalent C program.

I am new to Rust so I would like some feedback on my code. In particular, is my code in the correct Rust style?

I am aware of some changes to make the algorithm faster, but I would prefer feedback on the style of Rust code instead.

use std::env;
use std::fs::File;
use std::io::{Write, BufWriter};

fn prime_sieve(n: usize, ofile: &String) -> u32 {
let f = File::create(ofile).expect("Unable to create file");
let mut f = BufWriter::new(f);

let mut prime_mask: Vec<bool> = vec![true;n];
let mut p = 2;  // First prime number

let mut count = 0;  // Total number of primes found
let mut i;

// Main sieve loop
while p<n {
f.write_all(format!("{}\n",p).as_bytes())
.expect("Unable to write to file");
count+=1;
i=2*p;
while i<n {
i += p;
}
}
p+=1;
}
count
}

fn main() {
let args: Vec<String> = env::args().collect();
let n: usize = args
.trim()
.parse()
.expect("Wanted a number");
let ofile = &args;
let np = prime_sieve(n,ofile);
println!("Found {} primes less than {}. Wrote to {}", np, n, &args);
}


1. Learn to love rustfmt.

1. Spaces go around operators

- count+=1;
+ count += 1;

- i=2*p;
+ i = 2 * p;

- while i<n {
+ while i < n {

2. Spaces go between function arguments

- let np = prime_sieve(n,ofile);
+ let np = prime_sieve(n, ofile);

3. Spaces go after the ; in array and Vec declarations.

- vec![true;n];
+ vec![true; n];

2. There's no need to specify the type of prime_mask at all, inference can handle it.

3. Instead of comments, make your code tell the story. Introduce constants with names and rename existing variables.

4. "N" usually infers a count of something. For prime numbers, I'd expect N to mean "return me the first N primes". In this case, it's "check the first N numbers to see if they are prime". A better name would help communicate that.

5. Do not declare variables with a wider scope than you need. i can be declared where it is initialized.

6. Loops where you add one each iteration can be replaced with range-based for loops. Note that this removes mutability from your code.

7. Use write! instead of allocating a String and writing that.

8. Use writeln! instead of specifying the newline yourself,

9. There's no need to specify the inner type of the args vector. Use _ to let the compiler infer it.

10. Instead of hard-coding the concept of "files" into your prime_sieve function, accept any type that implements Write. Makes it easier to test.

use std::env;
use std::fs::File;
use std::io::{Write, BufWriter};

fn prime_sieve<W>(max_number_to_check: usize, mut output: W) -> u32
where W: Write
{
let mut prime_mask = vec![true; max_number_to_check];

let mut total_primes_found = 0;

const FIRST_PRIME_NUMBER: usize = 2;
for p in FIRST_PRIME_NUMBER..max_number_to_check {
writeln!(output, "{}", p).expect("Unable to write to file");
total_primes_found += 1;
let mut i = 2 * p;
while i < max_number_to_check {
i += p;
}
}
}

total_primes_found
}

fn main() {
let args: Vec<_> = env::args().collect();
let n: usize = args.trim().parse().expect("Wanted a number");

let ofile = &args;
let f = File::create(ofile).expect("Unable to create file");
let f = BufWriter::new(f);

let np = prime_sieve(n, f);

println!("Found {} primes less than {}. Wrote to {}", np, n, ofile);
}


For your usage, a Vec<bool> wastes space. Each bool is one byte, of which you are using a single bit. Instead, there are efficient bit vector crates which pack the data much tighter.

isn't there an advantage to explicitly putting in the types as it adds self documentation to the program? I come from Haskell which also has inferred typing but explicit type signatures are encouraged.

Explicit type signatures are required in Rust; you cannot infer the argument or return types of a function. Rust learned from Haskell here and avoided the problem of spooky action at a distance that can occur if you don't provide signatures.

Inference inside a function is quite idiomatic. There are times where you need to be explicit (such as the collection type to collect into), but beyond that, I shy away from listing any types.

I've a feeling this is something that changes as you grow accustomed to Rust. Beginners are more likely to sprinkle types about, then you learn to trust and rely on inference.

If there's ambiguity, it may be something that improving the variable name can help. As an example, to me a "mask" is a integral number that is applied using bitwise operations to another integer. I wouldn't expect for it to be a Vec.

I also use highly dynamic languages like Ruby where there are no static types, so the lack of types inside a function is not outrageous.

For Vec<bool> types, are they always a waste of space to use? Is there a case where they should be used instead of bit-vec types?

Every data structure has tradeoffs. The primary one I'm aware of is that a bit vector does not allow you to get a reference to the specific boolean value because a boolean doesn't really exist.

• Thanks for the feedback, all your points seem reasonable and I have some follow up questions: For points (3) and (10), isn't there an advantage to explicitly putting in the types as it adds self documentation to the program? I come from Haskell which also has inferred typing but explicit type signatures are encouraged. For Vec<bool> types, are they always a waste of space to use? Is there a case where they should be used instead of bit-vec types? – user668074 Mar 21 '17 at 2:44
• @user668074 updated – Shepmaster Mar 21 '17 at 13:02