Trait nekolib::math::Factors

source ·
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);

Required Associated Types§

Required Methods§

source

fn factors(self) -> Self::Output

Implementations on Foreign Types§

source§

impl Factors for usize

source§

impl Factors for u32

source§

impl Factors for u8

source§

impl Factors for u16

source§

impl Factors for u64

source§

impl Factors for u128

Implementors§