Trait nekolib::math::factors_dup::FactorsDup

pub trait FactorsDup {
    type Output;

    // Required method
    fn factors_dup(self) -> Self::Output;
}

素因数分解。

$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);

Required Associated Types

type Output

Required Methods

fn factors_dup(self) -> Self::Output

Implementations on Foreign Types

impl FactorsDup for u64

type Output = FactorsDupStruct<u64>

fn factors_dup(self) -> Self::Output

impl FactorsDup for u128

type Output = FactorsDupStruct<u128>

fn factors_dup(self) -> Self::Output

impl FactorsDup for u8

type Output = FactorsDupStruct<u8>

fn factors_dup(self) -> Self::Output

impl FactorsDup for usize

type Output = FactorsDupStruct<usize>

fn factors_dup(self) -> Self::Output

impl FactorsDup for u32

type Output = FactorsDupStruct<u32>

fn factors_dup(self) -> Self::Output

impl FactorsDup for u16

type Output = FactorsDupStruct<u16>

fn factors_dup(self) -> Self::Output

Implementors