prime_data/data/factors/
mod.rs

1//! Module dedicated to factorizing numbers
2use super::{PrimeData, utils::IntSqrt};
3use std::collections::HashMap;
4
5/// Retrieves every factor of x
6/// 
7/// *This function is only available with the `factors` feature enabled.*
8/// 
9/// A factor is any number that divides x. Therefore, it includes 1 and x itself.
10/// 
11/// This function is simply an abstraction over creating the [`Factorization`] struct
12/// and calling [`Factorization::all_factors`].
13/// 
14/// **Note**: The returned vector will have length 1, if and only if x is 1. It will have
15/// length 2 if and only if x is prime. However, it's much faster to verify if a number
16/// is prime using [PrimeData](`crate::PrimeData`).
17/// 
18/// # Examples
19/// 
20/// ```
21/// use prime_data::all_factors_of;
22/// 
23/// assert_eq!(all_factors_of(1), vec![1]);
24/// assert_eq!(all_factors_of(3), vec![1, 3]);
25/// assert_eq!(all_factors_of(6), vec![1, 2, 3, 6]);
26/// ```
27pub fn all_factors_of(x: u64) -> Vec<u64> {
28    Factorization::from(x).all_factors()
29}
30
31/// Represents some number into its prime-factorized form
32/// 
33/// *This struct is only available with the `factors` feature enabled.*
34pub struct Factorization {
35    data: HashMap<u64, u32>
36}
37
38impl Factorization {
39    /// Converts some factorization into the original number without consuming itself
40    /// 
41    /// # Examples
42    ///
43    /// ```
44    /// use prime_data::Factorization;
45    /// 
46    /// assert_eq!(1, Factorization::from(1).as_u64());
47    /// assert_eq!(12, Factorization::from(12).as_u64());
48    /// assert_eq!(29375346, Factorization::from(29375346).as_u64());
49    /// ```
50    pub fn as_u64(&self) -> u64 {
51        self.data.iter()
52        .fold(1u64, |acc, (&prime, &amount)| acc * prime.pow(amount))
53    }
54
55    /// Retrieves the factorization as a tuple (prime, amount)
56    /// 
57    /// Note that if the vector is empty, it means the original number is 1.
58    /// 
59    /// # Examples
60    /// 
61    /// ```
62    /// use prime_data::Factorization;
63    /// 
64    /// // 43560 = 2^3 * 3^2 * 5 * 11^2
65    /// let factorization = Factorization::from(43560);
66    /// assert_eq!(
67    ///     factorization.as_tuples(),
68    ///     vec![(2, 3), (3, 2), (5, 1), (11, 2)]
69    /// );
70    /// ```
71    pub fn as_tuples(&self) -> Vec<(u64, u32)> {
72        let mut vec: Vec<(u64, u32)> = self.data.iter().map(|(&p, &c)| (p, c)).collect();
73        vec.sort_by(|a, b| a.0.cmp(&(b.0)));
74
75        vec
76    }
77
78    /// Retrieves all possible factors of the factorized number
79    /// 
80    /// It does so by multiplying every possible combination of its prime factors.
81    /// 
82    /// **Note**: Includes 1 and itself. Therefore, the minimal length for this vector
83    /// is 1, happening when the original numbers is 1, then length 2, if and only if
84    /// the original number is prime.
85    /// 
86    /// # Examples
87    /// 
88    /// ```
89    /// use prime_data::Factorization;
90    /// 
91    /// let thirty = Factorization::from(30);
92    /// assert_eq!(
93    ///     thirty.all_factors(),
94    ///     vec![1, 2, 3, 5, 6, 10, 15, 30]
95    /// );
96    /// ```
97    pub fn all_factors(&self) -> Vec<u64> {
98        let tuples = self.as_tuples();
99        let mut vector = Self::factor_combos(&tuples);
100        vector.sort();
101
102        vector
103    }
104}
105
106// private methods
107impl Factorization {
108    pub(crate) fn new() -> Self {
109        Self { data: HashMap::new() }
110    }
111
112    pub(crate) fn add_factor(&mut self, factor: u64) {
113        if let Some(amount) = self.data.get_mut(&factor) {
114            *amount += 1;
115        } else {
116            self.data.insert(factor, 1);
117        }
118    }
119
120    pub(crate) fn is_empty(&self) -> bool {
121        self.data.is_empty()
122    }
123
124    fn factor_combos(slice: &[(u64, u32)]) -> Vec<u64> {
125        if slice.len() == 0 {
126            vec![1]
127        } else {
128            let inner_combos = Self::factor_combos(&slice[1..]);
129            let (this_prime, amount) = slice[0];
130
131            let mut combinations = Vec::new();
132            for pow in 0..=amount {
133                let new_factor = this_prime.pow(pow);
134                combinations.append(&mut (inner_combos.iter().map(|&x| new_factor * x).collect()));
135            }
136
137            combinations
138        }
139    }
140}
141
142impl From<u64> for Factorization {
143    fn from(number: u64) -> Factorization {
144        let prime_data = PrimeData::generate(0..=(number.sqrt_floor()));
145
146        prime_data.factorize(number)
147    }
148}
149
prime_data/data/factors/mod.rs

prime_data/data/factors/
mod.rs
