Prime Sieve of Eratosthenes in Rust

main.rs

// Created and tested at: rustc 0.13.0-nightly

extern crate test;

use std::num::Float;

/// Given the limit `end` the method will find all prime values below that limit
fn get_primes_below_n(end: uint) -> Option<Vec<uint>> {
    // If the parameter is less than two then we know that there cannot be any
    // prime values found so return None
    if end < 2u {
        return None
    }

    // Create a filter vector with all values set to true
    let mut ar: Vec<bool> = Vec::from_elem(end, true);
    
    // Determine the approximate number of primes that we are likely to find
    // and use that value to create a vector with an inital capacity to hold
    // them all (https://primes.utm.edu/howmany.html)
    let n = end as f64;
    let approx_num_primes = ((n / n.ln()) * (1f64 + (1.2762 / n.ln()))) as uint;
    let mut primes: Vec<uint> = Vec::with_capacity(approx_num_primes);

    // Add the first prime value, there is no need to attempt to determine it
    primes.push(2u);

    // Determine a limiting value.  Any prime numbers found below this value will
    // have their mutiples flag flipped, after this value we do not need to perform
    // this function
    let limit = (((end as f64).sqrt()) as uint) + 1;

    // Step through each odd value
    for i in std::iter::range_step(3u, end, 2u) {
        if ar[i] {
            // If the current value is true then it is prime so add it to the list
            primes.push(i);
            if i < limit {
                // If the value of i is below the limit then flip each multiple
                // of the value starting from its square
                for j in std::iter::range_step(i * i, end, i) {
                    ar[j] = false;
                }
            }
        }
    }

    // Return the collection of primes
    Some(primes)
}

#[cfg(not(test))]
fn main() {
    let primes = get_primes_below_n(1000000u);
    match primes {
        None    => println!("No primes found"),
        Some(p) => println!("The largest prime less than 1 million is: {}", p[p.len() - 1]),
    }
}

#[cfg(test)]
mod tests {
    use super::get_primes_below_n;
    use test::Bencher;

    #[test]
    fn end_equalto_1() {
        let p = get_primes_below_n(1u);
        assert_eq!(None, p);
    }

    #[test]
    fn end_equalto_3() {
        let primes = get_primes_below_n(3u);
        match primes {
            None    => assert!(false),
            Some(p) => assert_eq!(p, vec!(2u)),
        }
    }

    #[test]
    fn end_equalto_10() {
        let primes = get_primes_below_n(10u);
        match primes {
            None    => assert!(false),
            Some(p) => assert_eq!(p, vec!(2u, 3, 5, 7)),
        }
    }

    #[test]
    fn end_equalto_1million() {
        let primes = get_primes_below_n(1000000u);
        match primes {
            None    => assert!(false),
            Some(p) => assert_eq!(p[p.len() - 1], 999983u),
        }
    }

    #[bench]
    fn bench_for_n_equalto_1000(b: &mut Bencher) {
        b.iter(|| {
            get_primes_below_n(1000u)
        });
    }
}