Trait nekolib::math::factors_dup::FactorsDup
source · pub trait FactorsDup {
type Output;
// Required method
fn factors_dup(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.
use nekolib::math::FactorsDup;
let n = 735134400_u64;
let fac: Vec<_> = n.factors_dup().collect();
assert_eq!(fac, [2, 2, 2, 2, 2, 2, 3, 3, 3, 5, 5, 7, 11, 13, 17]);
assert_eq!(fac.iter().product::<u64>(), n);
assert_eq!(
(2_u64.pow(5) * 3_u64.pow(5)).factors_dup().product::<u64>(),
6_u64.pow(5)
);
assert_eq!(1_u64.factors_dup().next(), None);