dsalgo/
prime_factorize_pollard_rho.rs

1use crate::{
2    make_sparse_histogram::make_sparse_histogram,
3    prime_factorize_pollard_rho_flat::*,
4};
5
6pub fn prime_factorize_pollard_rho<F>(
7    is_prime: &F,
8    n: u64,
9) -> Result<Vec<(u64, u8)>, &'static str>
10where
11    F: Fn(u64) -> bool,
12{
13    Ok(make_sparse_histogram(prime_factorize_flat_pollard_rho(is_prime, n)?)
14        .into_iter()
15        .map(|(p, c)| (p, c as u8))
16        .collect())
17}
18
19#[cfg(test)]
20
21mod tests {
22
23    #[test]
24
25    fn test() {
26        use super::*;
27        use crate::{
28            primality::test::mr::*,
29            prime_factorize_trial_division::*,
30        };
31
32        for i in 1..10000 {
33            assert_eq!(
34                prime_factorize_pollard_rho(&is_p, i),
35                Ok(prime_factorize(i)),
36            );
37        }
38    }
39}