Computes all primes up to a certain number.

eratosthenes.rs

use std::env;

fn main() {
    let n = env::args()
        .nth(1)
        .expect("missing required argument")
        .parse()
        .expect("expected a valid number");

    let primes = sieve(n);
    println!("Found {} primes up to {}.", primes.len(), n);
    println!("{:?}", primes);
}

fn sieve(n: usize) -> Vec<usize> {
    let mut primes = vec![2];
    let upper = n / 2 - 1;
    let mut non_primes = vec![false; upper];

    let mut i = 0;
    while i < upper {
        if !non_primes[i] {
            let p = 2 * i + 3;
            primes.push(p);

            let mut j = (p * p - 3) / 2;
            while j < upper {
                non_primes[j] = true;
                j += p;
            }
        }

        i += 1;
    }

    primes
}

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

    #[test]
    fn test_sieve_finds_all_primes_up_to_60() {
        assert_eq!(
            sieve(60),
            vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59],
        );
    }
}