rust/sieve/src/lib.rs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

pub fn primes_up_to(upper_bound: u64) -> Vec<u64> {
    let mut sieve: Vec<Option<u64>> = (2..=upper_bound).map(Some).collect();
    primes(&mut sieve);
    sieve.iter().filter_map(|x| *x).collect()
}

fn primes(ps: &mut [Option<u64>]) {
    if let Some(&n) = ps.first() {
        if let Some(p) = n {
            (p as usize..ps.len())
                .step_by(p as usize)
                .for_each(|x| ps[x] = None)
        }
        primes(&mut ps[1..]);
    }
}