pub trait Factors {
type Output;
// Required method
fn factors(self) -> Self::Output;
}Expand description
素因数分解。
$n = \prod_{p_i:\text{ prime}} p_i^{e_i}$ に対して、各 $(p_i, e_i)$ を $p_i$ の昇順に返す。
Complexity
$O(\sqrt{n})$ time, $O(1)$ space.
Examples
use nekolib::math::Factors;
let n = 735134400_u64;
let fac: Vec<_> = n.factors().collect();
assert_eq!(fac, [(2, 6), (3, 3), (5, 2), (7, 1), (11, 1), (13, 1), (17, 1)]);
assert_eq!(fac.iter().map(|&(p, e)| p.pow(e)).product::<u64>(), n);
assert_eq!(1_u64.factors().next(), None);