sieve/
sieve.rs

1use quickcheck::quickcheck;
2
3fn sieve(n: usize) -> Vec<usize> {
4    if n <= 1 {
5        return vec![];
6    }
7
8    let mut marked = vec![false; n + 1];
9    marked[0] = true;
10    marked[1] = true;
11    marked[2] = true;
12    for p in 2..n {
13        for i in (2 * p..n).filter(|&n| n % p == 0) {
14            marked[i] = true;
15        }
16    }
17    marked
18        .iter()
19        .enumerate()
20        .filter_map(|(i, &m)| if m { None } else { Some(i) })
21        .collect()
22}
23
24fn is_prime(n: usize) -> bool {
25    n != 0 && n != 1 && (2..).take_while(|i| i * i <= n).all(|i| n % i != 0)
26}
27
28fn main() {
29    fn prop_all_prime(n: usize) -> bool {
30        sieve(n).into_iter().all(is_prime)
31    }
32
33    fn prop_prime_iff_in_the_sieve(n: usize) -> bool {
34        sieve(n) == (0..(n + 1)).filter(|&i| is_prime(i)).collect::<Vec<_>>()
35    }
36
37    quickcheck(prop_all_prime as fn(usize) -> bool);
38    quickcheck(prop_prime_iff_in_the_sieve as fn(usize) -> bool);
39}
sieve/sieve.rs

sieve/
sieve.rs
