dsalgo/
prime_factorize_with_least_prime_factor_table_u32.rs

1use crate::least_prime_factor_table_with_sieve_of_eratosthenes_u32::*;
2
3pub struct PrimeFactorize {
4    lpf: Vec<Option<u32>>,
5}
6
7impl PrimeFactorize {
8    pub fn new(size: usize) -> Self {
9        Self { lpf: least_prime_factor(size) }
10    }
11
12    pub fn factorize(
13        &self,
14        mut n: u32,
15    ) -> Vec<(u32, u32)> {
16        assert!((n as usize) < self.lpf.len());
17
18        let mut factors = vec![];
19
20        while n > 1 {
21            let p = self.lpf[n as usize].unwrap();
22
23            let mut e = 0;
24
25            while n % p == 0 {
26                n /= p;
27
28                e += 1;
29            }
30
31            factors.push((p, e));
32        }
33
34        factors
35    }
36}
37
38#[cfg(test)]
39
40mod tests {
41
42    #[test]
43
44    fn test() {}
45}