1  use quickcheck::quickcheck;
2  
sieve(n: usize) -> Vec<usize>3  fn 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  
is_prime(n: usize) -> bool24  fn is_prime(n: usize) -> bool {
25      n != 0 && n != 1 && (2..).take_while(|i| i * i <= n).all(|i| n % i != 0)
26  }
27  
main()28  fn 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  }
40