fast_factor/
lib.rs

1//! A reasonably fast factorisation library for unsigned integers.
2//!
3//! # Examples
4//!
5//! ```
6//! assert_eq!(fast_factor::factor(24_u32), vec![1,2,3,4,6,8,12,24]);
7//! assert_eq!(fast_factor::proper_factor(24_u32), vec![1,2,3,4,6,8,12]);
8//! assert_eq!(fast_factor::exclusive_factor(24_u32), vec![2,3,4,6,8,12]);
9//! assert!(!fast_factor::is_prime(24_u32));
10//! ```
11
12use num_integer::Roots;
13use num_traits::{PrimInt, Unsigned};
14
15/// For non-zero be unsigned integer inputs, returns all factors of the number given, including one and the number itself, as a vector. Returns an empty vector for zero.
16///
17/// # Examples
18///
19/// ```
20/// assert_eq!(fast_factor::factor(0_u32), vec![]);
21/// assert_eq!(fast_factor::factor(1_u32), vec![1]);
22/// assert_eq!(fast_factor::factor(7_u32), vec![1,7]);
23/// assert_eq!(fast_factor::factor(12_u32), vec![1,2,3,4,6,12]);
24/// assert_eq!(fast_factor::factor(36_u32), vec![1,2,3,4,6,9,12,18,36]);
25/// ```
26pub fn factor<T: PrimInt + Unsigned + Roots>(n: T) -> Vec<T> {
27    let mut factors: Vec<T> = Vec::new();
28    let zero = T::zero();
29    let one = T::one();
30    let two = one + one;
31    if n == zero {
32        return factors;
33    }
34
35    factors.push(one);
36    let root_n = n.sqrt();
37    let mut factor = two;
38    while factor <= root_n {
39        if n % factor == zero {
40            factors.push(factor);
41        }
42        factor = factor + one;
43    }
44    let is_square = root_n * root_n == n;
45    let mid = factors.len();
46    for index in (0..mid).rev() {
47        let factor = factors[index];
48        if !(is_square && factor == root_n) {
49            factors.push(n / factor);
50        }
51    }
52    factors
53}
54
55/// For all unsigned integer inputs, returns all factors of the number, excluding the number
56/// itself.
57///
58/// # Examples
59///
60/// ```
61/// assert_eq!(fast_factor::proper_factor(0_u32), vec![]);
62/// assert_eq!(fast_factor::proper_factor(1_u32), vec![]);
63/// assert_eq!(fast_factor::proper_factor(7_u32), vec![1]);
64/// assert_eq!(fast_factor::proper_factor(12_u32), vec![1,2,3,4,6]);
65/// assert_eq!(fast_factor::proper_factor(36_u32), vec![1,2,3,4,6,9,12,18]);
66/// ```
67pub fn proper_factor<T: PrimInt + Unsigned + Roots>(n: T) -> Vec<T> {
68    let mut factors: Vec<T> = Vec::new();
69
70    let zero = T::zero();
71    let one = T::one();
72    let two = one + one;
73
74    if n < two {
75        return factors;
76    }
77
78    factors.push(one);
79    let root_n = n.sqrt();
80
81    let mut factor = two;
82    while factor <= root_n {
83        if n % factor == zero {
84            factors.push(factor);
85        }
86        factor = factor + one;
87    }
88    let is_square = root_n * root_n == n;
89    let mid = factors.len();
90    for index in (1..mid).rev() {
91        let factor = factors[index];
92        if !(is_square && factor == root_n) {
93            factors.push(n / factor);
94        }
95    }
96    factors
97}
98
99/// For all unsigned integer inputs, returns all factors of the number, excluding one and the number
100/// itself.
101///
102/// # Examples
103///
104/// ```
105/// assert_eq!(fast_factor::exclusive_factor(0_u32), vec![]);
106/// assert_eq!(fast_factor::exclusive_factor(1_u32), vec![]);
107/// assert_eq!(fast_factor::exclusive_factor(7_u32), vec![]);
108/// assert_eq!(fast_factor::exclusive_factor(12_u32), vec![2,3,4,6]);
109/// assert_eq!(fast_factor::exclusive_factor(36_u32), vec![2,3,4,6,9,12,18]);
110/// ```
111pub fn exclusive_factor<T: PrimInt + Unsigned + Roots>(n: T) -> Vec<T> {
112    let mut factors: Vec<T> = Vec::new();
113
114    let zero = T::zero();
115    let one = T::one();
116    let two = one + one;
117
118    if n < two + two {
119        return factors;
120    }
121
122    let root_n = n.sqrt();
123
124    let mut factor = two;
125    while factor <= root_n {
126        if n % factor == zero {
127            factors.push(factor);
128        }
129        factor = factor + one;
130    }
131    let is_square = root_n * root_n == n;
132    let mid = factors.len();
133    for index in (0..mid).rev() {
134        let factor = factors[index];
135        if !(is_square && factor == root_n) {
136            factors.push(n / factor);
137        }
138    }
139    factors
140}
141
142/// For all unsigned integer inputs, returns whether the number is prime. 0 and 1 are not.
143///
144/// # Examples
145///
146/// ```
147/// assert!(!fast_factor::is_prime(0_u32));
148/// assert!(!fast_factor::is_prime(1_u32));
149/// assert!(fast_factor::is_prime(7_u32));
150/// assert!(!fast_factor::is_prime(12_u32));
151/// assert!(!fast_factor::is_prime(36_u32));
152/// ```
153pub fn is_prime<T: PrimInt + Unsigned + Roots>(n: T) -> bool {
154    let zero = T::zero();
155    let one = T::one();
156    let two = one + one;
157
158    if n < two {
159        return false;
160    }
161
162    let root_n = n.sqrt();
163
164    let mut factor = two;
165    while factor <= root_n {
166        if n % factor == zero {
167            return false;
168        }
169        factor = factor + one;
170    }
171    true
172}
fast_factor/lib.rs

fast_factor/
lib.rs
