Trait Factor

pub trait Factor {
    type FACTORS;

    // Required method
    fn factor(&self) -> Self::FACTORS;
}

A trait for finding the prime factorization of a number.

Required Associated Types

type FACTORS

Required Methods

fn factor(&self) -> Self::FACTORS

Implementations on Foreign Types

impl Factor for u8

fn factor(&self) -> Factors<u8, MAX_FACTORS_IN_U8>

Returns the prime factorization of a u8. The return value is iterable, and produces pairs $(p,e)$ of type (u8, u8), where the $p$ is prime and $e$ is the exponent of $p$. The primes are in ascending order.

Worst-case complexity

Constant time and additional memory.

Panics

Panics if self is 0.

Examples

use itertools::Itertools;
use malachite_base::num::factorization::traits::Factor;

assert_eq!(251u8.factor().into_iter().collect_vec(), &[(251, 1)]);
assert_eq!(
    120u8.factor().into_iter().collect_vec(),
    &[(2, 3), (3, 1), (5, 1)]
);

type FACTORS = Factors<u8, MAX_FACTORS_IN_U8>

impl Factor for u16

fn factor(&self) -> Factors<u16, MAX_FACTORS_IN_U16>

Returns the prime factorization of a u16. The return value is iterable, and produces pairs $(p,e)$ of type (u16, u8), where the $p$ is prime and $e$ is the exponent of $p$. The primes are in ascending order.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(2^n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0.

Examples

use itertools::Itertools;
use malachite_base::num::factorization::traits::Factor;

assert_eq!(65521u16.factor().into_iter().collect_vec(), &[(65521, 1)]);
assert_eq!(
    40320u16.factor().into_iter().collect_vec(),
    &[(2, 7), (3, 2), (5, 1), (7, 1)]
);

type FACTORS = Factors<u16, MAX_FACTORS_IN_U16>

impl Factor for u32

fn factor(&self) -> Factors<u32, MAX_FACTORS_IN_U32>

Returns the prime factorization of a u32. The return value is iterable, and produces pairs $(p,e)$ of type (u32, u8), where the $p$ is prime and $e$ is the exponent of $p$. The primes are in ascending order.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(2^n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0.

Examples

use itertools::Itertools;
use malachite_base::num::factorization::traits::Factor;

assert_eq!(
    4294967291u32.factor().into_iter().collect_vec(),
    &[(4294967291, 1)]
);
assert_eq!(
    479001600u32.factor().into_iter().collect_vec(),
    &[(2, 10), (3, 5), (5, 2), (7, 1), (11, 1)]
);

This is n_factor when FLINT64 is false, from ulong_extras/factor.c, FLINT 3.1.2.

type FACTORS = Factors<u32, MAX_FACTORS_IN_U32>

impl Factor for u64

fn factor(&self) -> Factors<u64, MAX_FACTORS_IN_U64>

Returns the prime factorization of a u64. The return value is iterable, and produces pairs $(p,e)$ of type (u64, u8), where the $p$ is prime and $e$ is the exponent of $p$. The primes are in ascending order.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(2^n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0.

Examples

use itertools::Itertools;
use malachite_base::num::factorization::traits::Factor;

assert_eq!(
    18446744073709551557u64.factor().into_iter().collect_vec(),
    &[(18446744073709551557, 1)]
);
assert_eq!(
    2432902008176640000u64.factor().into_iter().collect_vec(),
    &[(2, 18), (3, 8), (5, 4), (7, 2), (11, 1), (13, 1), (17, 1), (19, 1)]
);

This is n_factor when FLINT64 is true, from ulong_extras/factor.c, FLINT 3.1.2.

type FACTORS = Factors<u64, MAX_FACTORS_IN_U64>

impl Factor for usize

fn factor(&self) -> Factors<usize, MAX_FACTORS_IN_USIZE>

Returns the prime factorization of a usize. The return value is iterable, and produces pairs $(p,e)$ of type (usize, u8), where the $p$ is prime and $e$ is the exponent of $p$. The primes are in ascending order.

Worst-case complexity

$T(n) = O(2^{n/4})$

$M(n) = O(2^n)$

where $T$ is time, $M$ is additional memory, and $n$ is self.significant_bits().

Panics

Panics if self is 0.

Examples

use itertools::Itertools;
use malachite_base::num::factorization::traits::Factor;

assert_eq!(
    4294967291usize.factor().into_iter().collect_vec(),
    &[(4294967291, 1)]
);
assert_eq!(
    479001600usize.factor().into_iter().collect_vec(),
    &[(2, 10), (3, 5), (5, 2), (7, 1), (11, 1)]
);

type FACTORS = Factors<usize, MAX_FACTORS_IN_USIZE>

Implementors