Struct prime_factorization::Factorization

pub struct Factorization<T: UInt> {
    pub num: T,
    pub is_prime: bool,
    pub factors: Vec<T>,
}

Fields

num: T

is_prime: bool

factors: Vec<T>

Implementations

impl<T: 'static + UInt> Factorization<T>

pub fn run(num: T) -> Self

Factorize a positive natural number num to its prime factors.

After the call, factors field of the struct contains all the prime factors, smallest prime being the first element in the container. Field num has the original number and field is_prime indicates whether the number is prime.

Examples

Factorize natural number 1729

use prime_factorization::Factorization;

let factor_repr = Factorization::<u32>::run(1729);

assert_eq!(factor_repr.factors, vec![7, 13, 19]);

Check whether 1801 is a prime number (no other factors than it itself)

use prime_factorization::Factorization;

let num = 1801u32;
let factor_repr = Factorization::run(num);

assert_eq!(factor_repr.is_prime, true);

assert_eq!(factor_repr.factors, vec![num]);

pub fn prime_factor_repr(&self) -> Vec<(T, u32)>

Get the prime factor representation for the natural number num: num = prm_1^k_1 * prm_2^k_2 * … * prm_n^k_n.

Representation is returned such that each element of the container is a tuple with the prime factor prm_i and its count k_i as its two elements, ordered s.t. the first tuple has the smallest prime.

This method assumes that the factors field has the correct prime factors sorted from smallest to largest and as such the representation can be directly produced from them.

Hence, always call the run associated function first.

Examples

use prime_factorization::Factorization;

let num = 491_520u32;

// Run first the factorization, which is 2^15 * 3 * 5 for `num`
let factor_repr = Factorization::run(num);

assert_eq!(factor_repr.prime_factor_repr(), vec![(2, 15), (3, 1), (5, 1)]);

Trait Implementations

impl<T: Debug + UInt> Debug for Factorization<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: UInt> Display for Factorization<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.