haar_lib/math/prime_test/
eratosthenes.rs

1//! Eratosthenesの篩
2
3pub use crate::math::prime_test::CheckPrime;
4
5/// Eratosthenesの篩
6pub struct EratosthenesSieve {
7    data: Vec<bool>,
8}
9
10impl EratosthenesSieve {
11    /// `size`までの自然数の素数判定ができる`EratosthenesSieve`を構築する。
12    pub fn new(size: usize) -> Self {
13        let mut data = vec![true; size.div_ceil(2)];
14        data[0] = false;
15
16        let mut i = 3;
17        while i * i <= size {
18            if !data[i / 2] {
19                i += 2;
20                continue;
21            }
22
23            let mut j = i * i;
24            while j <= size {
25                data[j / 2] = false;
26                j += 2 * i;
27            }
28
29            i += 2;
30        }
31
32        EratosthenesSieve { data }
33    }
34}
35
36impl CheckPrime<usize> for EratosthenesSieve {
37    fn is_prime(&self, i: usize) -> bool {
38        if i == 2 {
39            true
40        } else if i % 2 == 0 {
41            false
42        } else {
43            self.data[i / 2]
44        }
45    }
46}