sieve/
sieve.rs

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

sieve/
sieve.rs
