prime_factorization/
lib.rs

1use least_prime_factors::least_prime_factors;
2
3/// 素因数分解
4///
5/// # Examples
6///
7/// ```
8/// use prime_factorization::{ByLeastPrimeFactors, PrimeFactorization, TrialDivision};
9///
10/// let trial_div = TrialDivision::new();
11/// let lpf = ByLeastPrimeFactors::new(90);
12///
13/// // 90 = 2 * 3 * 3 * 5
14/// assert_eq!(trial_div.factors(90_u32), vec![(2, 1), (3, 2), (5, 1)]);
15/// assert_eq!(lpf.factors(90), vec![(2, 1), (3, 2), (5, 1)]);
16/// ```
17pub trait PrimeFactorization<T> {
18    /// x の (素因数, べき) のベクタを返します
19    fn factors(&self, x: T) -> Vec<(T, u32)>;
20}
21
22/// 試し割りによる素因数分解
23#[derive(Debug, Clone)]
24pub struct TrialDivision;
25
26impl TrialDivision {
27    pub fn new() -> Self {
28        Self {}
29    }
30}
31
32impl Default for TrialDivision {
33    fn default() -> Self {
34        Self::new()
35    }
36}
37
38macro_rules! impl_prime_factorization {
39    ($($t:ty),+) => {
40        $(
41            impl PrimeFactorization<$t> for TrialDivision {
42                /// O(sqrt(x)) time
43                fn factors(&self, x: $t) -> Vec<($t, u32)> {
44                    let mut p_exp = Vec::new();
45                    let mut y = x;
46                    for p in 2.. {
47                        // p * p > x
48                        if p > x / p {
49                            break;
50                        }
51                        let mut exp = 0;
52                        while y % p == 0 {
53                            exp += 1;
54                            y /= p;
55                        }
56                        if exp > 0 {
57                            p_exp.push((p, exp));
58                        }
59                    }
60                    if y > 1 {
61                        p_exp.push((y, 1));
62                    }
63                    p_exp
64                }
65            }
66        )+
67    };
68}
69
70impl_prime_factorization!(usize, u32, u64);
71
72/// least prime factors による素因数分解
73#[derive(Debug, Clone)]
74pub struct ByLeastPrimeFactors {
75    lpf: Vec<usize>,
76}
77
78impl ByLeastPrimeFactors {
79    /// 素因数分解の前計算として [least prime factors](least_prime_factors::least_prime_factors) を求めます。
80    pub fn new(n: usize) -> Self {
81        let lpf = least_prime_factors(n);
82        Self { lpf }
83    }
84}
85
86impl PrimeFactorization<usize> for ByLeastPrimeFactors {
87    /// # Panics
88    ///
89    /// if `x` > `n`
90    ///
91    /// O(log(x)) time
92    fn factors(&self, x: usize) -> Vec<(usize, u32)> {
93        assert!(x < self.lpf.len());
94        let mut p_exp = Vec::new();
95        let mut x = x;
96        while x > 1 {
97            let p = self.lpf[x];
98            let mut exp = 0;
99            while x % p == 0 {
100                exp += 1;
101                x /= p;
102            }
103            p_exp.push((p, exp));
104        }
105        p_exp
106    }
107}
108
109#[cfg(test)]
110mod tests {
111    use crate::{ByLeastPrimeFactors, PrimeFactorization, TrialDivision};
112
113    #[test]
114    fn small_trial_division() {
115        let trial_div = TrialDivision::new();
116        assert_eq!(trial_div.factors(0_u32), vec![]);
117        assert_eq!(trial_div.factors(1_u32), vec![]);
118        assert_eq!(trial_div.factors(2_u32), vec![(2, 1)]);
119        assert_eq!(trial_div.factors(3_u32), vec![(3, 1)]);
120        assert_eq!(trial_div.factors(4_u32), vec![(2, 2)]);
121    }
122
123    #[test]
124    fn small_least_prime_factors() {
125        let lpf = ByLeastPrimeFactors::new(10);
126        assert_eq!(lpf.factors(0_usize), vec![]);
127        assert_eq!(lpf.factors(1_usize), vec![]);
128        assert_eq!(lpf.factors(2_usize), vec![(2, 1)]);
129        assert_eq!(lpf.factors(3_usize), vec![(3, 1)]);
130        assert_eq!(lpf.factors(4_usize), vec![(2, 2)]);
131    }
132
133    #[test]
134    fn test_trial_division() {
135        let trial_div = TrialDivision::new();
136        for n in 1_u32..=1000 {
137            let mut res = 1;
138            for (p, e) in trial_div.factors(n) {
139                res *= p.pow(e);
140            }
141            assert_eq!(res, n);
142        }
143    }
144
145    #[test]
146    fn test_least_prime_factors() {
147        let lpf = ByLeastPrimeFactors::new(1000);
148        for n in 1_usize..=1000 {
149            let mut res = 1;
150            for (p, e) in lpf.factors(n) {
151                res *= p.pow(e);
152            }
153            assert_eq!(res, n);
154        }
155    }
156}
prime_factorization/lib.rs

prime_factorization/
lib.rs
