prime_factorization/
lib.rs

1/// 非負整数を素因数分解です。
2pub trait PrimeFactorization: Sized {
3    /// (素因数, べき) のベクタを返します。
4    ///
5    /// # Examples
6    /// ```
7    /// use prime_factorization::PrimeFactorization;
8    ///
9    /// assert_eq!(2_u32.prime_factorization(), vec![(2, 1)]);
10    /// // 90 = 2 * 3 * 3 * 5
11    /// assert_eq!(90_u32.prime_factorization(), vec![(2, 1), (3, 2), (5, 1)]);
12    /// ```
13    fn prime_factorization(self) -> Vec<(Self, Self)>;
14}
15
16macro_rules! impl_prime_factorization {
17    ($($t:ty),+) => {
18        $(
19            impl PrimeFactorization for $t {
20                fn prime_factorization(self) -> Vec<(Self, Self)> {
21                    let mut res = Vec::new();
22                    let mut n = self;
23                    for k in ((2 as Self)..).take_while(|&k| k.saturating_mul(k) <= self) {
24                        if n % k == 0 {
25                            let mut e = 0;
26                            while n % k == 0 {
27                                e += 1;
28                                n /= k;
29                            }
30                            res.push((k, e));
31                        }
32                    }
33                    if n > 1 {
34                        res.push((n, 1));
35                    }
36                    res
37                }
38            }
39        )+
40    };
41}
42
43impl_prime_factorization!(usize, u32, u64);
44
45#[cfg(test)]
46mod tests {
47    use crate::PrimeFactorization;
48
49    #[test]
50    fn small_test() {
51        assert_eq!(0_u32.prime_factorization(), vec![]);
52        assert_eq!(1_u32.prime_factorization(), vec![]);
53        assert_eq!(2_u32.prime_factorization(), vec![(2, 1)]);
54        assert_eq!(3_u32.prime_factorization(), vec![(3, 1)]);
55        assert_eq!(4_u32.prime_factorization(), vec![(2, 2)]);
56    }
57
58    #[test]
59    fn test() {
60        for n in 1..1000 {
61            let f = (n as u32).prime_factorization();
62            let mut res = 1;
63            for (p, e) in f {
64                res *= p.pow(e);
65            }
66            assert_eq!(res, n);
67        }
68    }
69}
prime_factorization/lib.rs

prime_factorization/
lib.rs
