1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

/// 非負整数を素因数分解です。
pub trait PrimeFactorization: Sized {
    /// (素因数, べき) のベクタを返します。
    ///
    /// # Examples
    /// ```
    /// use prime_factorization::PrimeFactorization;
    ///
    /// assert_eq!(2_u32.prime_factorization(), vec![(2, 1)]);
    /// // 90 = 2 * 3 * 3 * 5
    /// assert_eq!(90_u32.prime_factorization(), vec![(2, 1), (3, 2), (5, 1)]);
    /// ```
    fn prime_factorization(self) -> Vec<(Self, Self)>;
}

macro_rules! impl_prime_factorization {
    ($($t:ty),+) => {
        $(
            impl PrimeFactorization for $t {
                fn prime_factorization(self) -> Vec<(Self, Self)> {
                    let mut res = Vec::new();
                    let mut n = self;
                    for k in ((2 as Self)..).take_while(|&k| k.saturating_mul(k) <= self) {
                        if n % k == 0 {
                            let mut e = 0;
                            while n % k == 0 {
                                e += 1;
                                n /= k;
                            }
                            res.push((k, e));
                        }
                    }
                    if n > 1 {
                        res.push((n, 1));
                    }
                    res
                }
            }
        )+
    };
}

impl_prime_factorization!(usize, u32, u64);

#[cfg(test)]
mod tests {
    use crate::PrimeFactorization;

    #[test]
    fn small_test() {
        assert_eq!(0_u32.prime_factorization(), vec![]);
        assert_eq!(1_u32.prime_factorization(), vec![]);
        assert_eq!(2_u32.prime_factorization(), vec![(2, 1)]);
        assert_eq!(3_u32.prime_factorization(), vec![(3, 1)]);
        assert_eq!(4_u32.prime_factorization(), vec![(2, 2)]);
    }

    #[test]
    fn test() {
        for n in 1..1000 {
            let f = (n as u32).prime_factorization();
            let mut res = 1;
            for (p, e) in f {
                res *= p.pow(e);
            }
            assert_eq!(res, n);
        }
    }
}