haar_lib/math/primality/
linear_sieve.rs

1//! 線形篩
2
3use crate::math::primality::PrimalityTest;
4
5/// 線形篩
6pub struct LinearSieve {
7    least_factors: Vec<usize>,
8}
9
10impl LinearSieve {
11    /// `n`までの自然数の素数判定ができる`LinearSieve`を返す。
12    pub fn new(n: usize) -> Self {
13        let mut least_factors = vec![0; n + 1];
14        let mut primes = vec![];
15
16        for d in 2..=n {
17            if least_factors[d] == 0 {
18                least_factors[d] = d;
19                primes.push(d);
20            }
21
22            for &p in &primes {
23                if p * d > n || p > least_factors[d] {
24                    break;
25                }
26                least_factors[p * d] = p;
27            }
28        }
29
30        Self { least_factors }
31    }
32
33    /// `n`の最小素因数を返す。
34    pub fn least_prime_factor(&self, n: usize) -> usize {
35        self.least_factors[n]
36    }
37}
38
39impl PrimalityTest<usize> for LinearSieve {
40    fn is_prime(&self, value: usize) -> bool {
41        if value == 0 {
42            return false;
43        }
44        self.least_factors[value] == value
45    }
46}
haar_lib/math/primality/linear_sieve.rs

haar_lib/math/primality/
linear_sieve.rs
