dsalgo/
prime_factorize_fermat.rs

1use crate::{
2    fermat_factorization_method::fermat_factorization_method,
3    make_sparse_histogram::make_sparse_histogram,
4};
5
6fn prime_factorize_flat_fermat(mut n: u64) -> Vec<u64> {
7    assert!(n > 0);
8
9    let mut res = vec![];
10
11    let ctz = n.trailing_zeros();
12
13    res.extend(vec![2; ctz as usize]);
14
15    n >>= ctz;
16
17    if n == 1 {
18        return res;
19    }
20
21    let a = fermat_factorization_method(n);
22
23    let b = n / a;
24
25    debug_assert!(a >= b && a * b == n);
26
27    if a == n {
28        res.push(a);
29    } else {
30        res.extend(prime_factorize_flat_fermat(a).into_iter());
31
32        res.extend(prime_factorize_flat_fermat(b).into_iter());
33    }
34
35    res
36}
37
38pub fn prime_factorize_fermat(n: u64) -> Vec<(u64, u8)> {
39    make_sparse_histogram(prime_factorize_flat_fermat(n))
40        .into_iter()
41        .map(|(p, c)| (p, c as u8))
42        .collect()
43}
44
45#[cfg(test)]
46
47mod tests {
48
49    #[test]
50
51    fn test() {
52        use super::*;
53        use crate::prime_factorize_trial_division::*;
54
55        for i in 1..100 {
56            assert_eq!(prime_factorize_fermat(i), prime_factorize(i));
57        }
58    }
59}
dsalgo/prime_factorize_fermat.rs

dsalgo/
prime_factorize_fermat.rs
