nums/
traits.rs

1use alloc::vec;
2use alloc::vec::Vec;
3use num_bigint::BigUint;
4
5pub trait PrimalityTest {
6    fn is_prime(&self, n: &BigUint) -> bool;
7}
8
9pub trait CompositeSplitter {
10    /// Undefined behavior if `n` is prime.
11    fn divisor(&self, n: &BigUint) -> BigUint;
12
13    fn split(&self, n: &BigUint) -> (BigUint, BigUint) {
14        let d = self.divisor(n);
15        (n / &d, d)
16    }
17}
18
19pub trait Factorizer {
20    fn factors(&self, n: &BigUint) -> Vec<BigUint>;
21
22    fn factor_counts(&self, n: &BigUint) -> Vec<(BigUint, usize)> {
23        let mut factors = self.factors(n);
24        factors.sort();
25        let mut factors_iter = factors.into_iter().peekable();
26        let mut factor_counts = vec![];
27        while let Some(f) = factors_iter.next() {
28            let mut count = 1;
29            while factors_iter.peek() == Some(&f) {
30                count += 1;
31                factors_iter.next();
32            }
33            factor_counts.push((f, count));
34        }
35        factor_counts
36    }
37}