primefactor/
lib.rs

1//! Module for factorizing integers
2#![deny(unsafe_code)]
3pub mod candidates;
4
5use std::cmp::{min, Ordering};
6use std::convert::From;
7use std::fmt;
8use candidates::{is_pw210_candidate, PrimeWheel210};
9
10#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
11pub struct IntFactor {
12    pub integer: u128,
13    pub exponent: u32,
14}
15
16impl IntFactor {
17    pub fn to_vec(&self) -> Vec<u128> {
18        vec![self.integer; self.exponent as usize]
19    }
20}
21
22impl fmt::Display for IntFactor {
23    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
24        if self.exponent > 1 {
25            write!(f, "{}^{}", self.integer, self.exponent)
26        } else {
27            write!(f, "{}", self.integer)
28        }
29    }
30}
31
32#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
33pub struct PrimeFactors {
34    factors: Vec<IntFactor>
35}
36
37impl PrimeFactors {
38    fn new() -> Self {
39        PrimeFactors { factors: Vec::with_capacity(8) }
40    }
41    fn add(&mut self, integer: u128, exponent: u32) {
42        self.factors.push(IntFactor { integer, exponent })
43    }
44    pub fn value(&self) -> u128 {
45        self.factors.iter().map(|f| f.integer.pow(f.exponent)).product()
46    }
47    pub fn len(&self) -> usize {
48        self.factors.len()
49    }
50    pub fn count_factors(&self) -> u32 {
51        self.factors.iter().map(|f| f.exponent).sum()
52    }
53    pub fn is_empty(&self) -> bool {
54        self.factors.is_empty()
55    }
56    pub fn is_prime(&self) -> bool {
57        self.count_factors() == 1
58    }
59    pub fn to_factor_vec(&self) -> &Vec<IntFactor> {
60        &self.factors
61    }
62    pub fn to_vec(&self) -> Vec<u128> {
63        let mut ret = Vec::new();
64        self.factors.iter().for_each(|f| ret.extend(f.to_vec()));
65        ret
66    }
67    pub fn gcd(&self, other: &PrimeFactors) -> PrimeFactors {
68        let mut pf = PrimeFactors::new();
69        if self.is_empty() || other.is_empty() { return pf; }
70        let mut s_it = self.factors.iter();
71        let mut o_it = other.factors.iter();
72        let mut s = s_it.next().unwrap();
73        let mut o = o_it.next().unwrap();
74        loop {
75            let prime_cmp = s.integer.cmp(&o.integer);
76            if prime_cmp == Ordering::Equal {
77                pf.add(s.integer, min(o.exponent, s.exponent));
78            }
79            match prime_cmp {
80                Ordering::Less | Ordering::Equal => {
81                    if let Some(n) = s_it.next() { s = n; } else { break; }
82                },
83                Ordering::Greater => {
84                    if let Some(n) = o_it.next() { o = n; } else { break; }
85                },
86            }
87        }
88        pf
89    }
90}
91
92impl From<u128> for PrimeFactors {
93    fn from(n: u128) -> Self {
94        let mut pf = PrimeFactors::new();
95        if n < 2 { return pf; }
96        // A factor of n must have a value less than or equal to sqrt(n)
97        let mut maxsq = n;
98        let mut x = n;
99        let pw_iter = PrimeWheel210::new();
100        for f in pw_iter {
101            if f * f > maxsq {
102                break;
103            }
104            let mut c = 0;
105            while x.is_multiple_of(f) {
106                x /= f;
107                c += 1;
108            }
109            if c > 0 {
110                // A factor of x squared must be less than or equal to x
111                maxsq = x;
112                pf.add(f, c);
113            }
114            if x == 1 {
115                break;
116            }
117        }
118        if x > 1 || pf.is_empty() {
119            // Any remainder must be the number itself or a factor of it.
120            pf.add(x, 1);
121        }
122        pf
123    }
124}
125
126impl fmt::Display for PrimeFactors {
127    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
128        let parts: Vec<_> = self.factors.iter()
129            .map(|f| f.to_string())
130            .collect();
131        write!(f, "{}", parts.join(" * "))
132    }
133}
134
135/// IntFactor interator
136impl<'a> IntoIterator for &'a PrimeFactors {
137    type Item = &'a IntFactor; // Items yielded by the iterator will be references
138    type IntoIter = std::slice::Iter<'a, IntFactor>; // Use a slice iterator
139
140    fn into_iter(self) -> Self::IntoIter {
141        self.factors.iter()  // Create a standard slice iterator
142    }
143}
144
145/// Test if the value is a prime number, or not
146pub fn u128_is_prime(n: u128) -> bool {
147    if !is_pw210_candidate(n) {
148        return false;
149    }
150    // A factor of n must have a value less than or equal to sqrt(n)
151    let pw_iter = PrimeWheel210::new();
152    for f in pw_iter {
153        if f * f > n {
154            break;
155        }
156        if n.is_multiple_of(f) {
157            return false;
158        }
159    }
160    true
161}
162
163/// Calculate the Greatest common divisor (GCD) between 2 unsigned integers
164pub fn primefactor_gcd(this: u128, that: u128) -> PrimeFactors {
165    let pf_this = PrimeFactors::from(this);
166    let pf_that = PrimeFactors::from(that);
167    pf_this.gcd(&pf_that)
168}
169
170/// Calculate the Greatest common divisor (GCD) between 2 unsigned integers.
171/// Based on Euclid's algorithm pseudo code at:
172/// https://en.wikipedia.org/wiki/Euclidean_algorithm
173pub fn u128_gcd(this: u128, that: u128) -> u128 {
174    let mut a = this;
175    let mut b = that;
176    while b > 0 {
177        let c = b;
178        b = a % b;
179        a = c;
180    }
181    a
182}
183
184/// Calculate the Least common multiple (LCM) for 2 integers
185pub fn u128_lcm(this: u128, that: u128) -> u128 {
186    if this == 0 && that == 0 { return 0; }
187    let gcd = u128_gcd(this, that);
188    this * that / gcd
189}
primefactor/lib.rs

primefactor/
lib.rs
