haar_lib/math/factorize/
sieve.rs

1//! 前計算による素因数分解
2
3/// 前計算による素因数分解
4///
5/// **Space complexity** $O(n)$
6pub struct FactorizeSieve {
7    p: Vec<usize>,
8}
9
10impl FactorizeSieve {
11    /// `n`以下の非負整数を素因数分解できる[`FactorizeSieve`]を構築する。
12    pub fn new(n: usize) -> Self {
13        let mut p = vec![0; n + 1];
14
15        for i in 2..=n {
16            if p[i] == 0 {
17                for j in (i..=n).step_by(i) {
18                    if p[j] == 0 {
19                        p[j] = i;
20                    }
21                }
22            }
23        }
24
25        Self { p }
26    }
27
28    /// `n`の素因数を列挙する。
29    pub fn factorize(&self, mut n: usize) -> Vec<usize> {
30        let mut ret = vec![];
31
32        while n > 1 {
33            ret.push(self.p[n]);
34            n /= self.p[n];
35        }
36
37        ret
38    }
39}
haar_lib/math/factorize/sieve.rs

haar_lib/math/factorize/
sieve.rs
