dsalgo/
sieve_of_sundaram_u32.rs

1//! sieve of sundaram
2
3pub fn enumerate_primes(less_than: u32) -> Vec<u32> {
4    let mut a = vec![];
5
6    if less_than <= 2 {
7        return a;
8    }
9
10    a.push(2);
11
12    let n = (less_than >> 1) as usize;
13
14    let mut is_p = vec![true; n];
15
16    for i in 1..n {
17        if is_p[i] {
18            a.push(((i as u32) << 1) | 1);
19        }
20
21        for j in (i * (i + 1) << 1..n).step_by((i << 1) | 1) {
22            is_p[j] = false;
23        }
24    }
25
26    a
27}
28
29#[cfg(test)]
30
31mod tests {
32
33    use super::enumerate_primes as sundaram;
34
35    #[test]
36
37    fn test() {
38        use crate::sieve_of_eratosthenes_enumerate_primes_u32::enumerate_primes;
39
40        let lim = [99, 100, 101, 102, 1 << 17];
41
42        for l in lim {
43            assert_eq!(sundaram(l), enumerate_primes(l));
44        }
45    }
46}