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

fast_factor/
lib.rs
