const_primes/cache/
prime_factors.rs

1use super::Underlying;
2
3use core::iter::FusedIterator;
4
5/// An iterator over the prime factors of a number and their multiplicities.
6///
7/// Created by the [`prime_factorization`](super::Primes::prime_factorization) function on [`Primes`](super::Primes),
8/// see it for more information.
9#[derive(Debug, Clone)]
10#[cfg_attr(
11    feature = "rkyv",
12    derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)
13)]
14#[must_use = "iterators are lazy and do nothing unless consumed"]
15pub struct PrimeFactorization<'a> {
16    primes_cache: &'a [Underlying],
17    cache_index: usize,
18    number: Underlying,
19}
20
21impl<'a> PrimeFactorization<'a> {
22    pub(crate) const fn new(primes_cache: &'a [Underlying], number: Underlying) -> Self {
23        Self {
24            primes_cache,
25            cache_index: 0,
26            number,
27        }
28    }
29
30    /// If the number contains prime factors that are larger than the largest prime
31    /// in the cache, this function returns their product.
32    #[must_use = "`self` will be dropped if the result is not used"]
33    pub fn remainder(mut self) -> Option<Underlying> {
34        for _ in self.by_ref() {}
35        if self.number > 1 {
36            Some(self.number)
37        } else {
38            None
39        }
40    }
41}
42
43impl Iterator for PrimeFactorization<'_> {
44    type Item = (Underlying, u8);
45    fn next(&mut self) -> Option<Self::Item> {
46        if self.number == 1 {
47            return None;
48        }
49
50        while let Some(prime) = self.primes_cache.get(self.cache_index) {
51            let mut count = 0;
52            while self.number % prime == 0 {
53                count += 1;
54                self.number /= prime;
55            }
56
57            self.cache_index += 1;
58
59            if count > 0 {
60                return Some((*prime, count));
61            }
62        }
63
64        None
65    }
66
67    #[inline]
68    fn size_hint(&self) -> (usize, Option<usize>) {
69        (0, Some(self.primes_cache.len() - self.cache_index))
70    }
71}
72
73impl FusedIterator for PrimeFactorization<'_> {}
74
75/// An iterator over the prime factors of a given number.
76///
77/// Created by the [`prime_factors`](super::Primes::prime_factors)
78/// function on [`Primes`](super::Primes), see it for more information.
79#[derive(Debug, Clone)]
80#[must_use = "iterators are lazy and do nothing unless consumed"]
81pub struct PrimeFactors<'a> {
82    primes_cache: &'a [Underlying],
83    cache_index: usize,
84    number: Underlying,
85}
86
87impl<'a> PrimeFactors<'a> {
88    #[inline]
89    pub(crate) const fn new(primes_cache: &'a [Underlying], number: Underlying) -> Self {
90        Self {
91            primes_cache,
92            cache_index: 0,
93            number,
94        }
95    }
96
97    /// If the number contains prime factors that are larger than the largest prime
98    /// in the cache, this function returns their product.
99    ///
100    /// It does this by doing all the work that [`PrimeFactorization`] would have done,
101    /// so the performance advantage of this iterator over that one disappears if this function is called.
102    #[inline]
103    #[must_use = "`self` will be dropped if the result is not used"]
104    pub fn remainder(self) -> Option<Underlying> {
105        // We haven't actually divided out any of the factors to save work,
106        // so we do that by just delegating to PrimeFactorization,
107        // which does the work in its implementation of this function.
108        PrimeFactorization::new(self.primes_cache, self.number).remainder()
109    }
110}
111
112impl Iterator for PrimeFactors<'_> {
113    type Item = Underlying;
114    fn next(&mut self) -> Option<Self::Item> {
115        while let Some(prime) = self.primes_cache.get(self.cache_index) {
116            self.cache_index += 1;
117            if self.number % prime == 0 {
118                return Some(*prime);
119            }
120        }
121
122        None
123    }
124
125    #[inline]
126    fn size_hint(&self) -> (usize, Option<usize>) {
127        (0, Some(self.primes_cache.len() - self.cache_index))
128    }
129}
130
131impl FusedIterator for PrimeFactors<'_> {}
const_primes/cache/prime_factors.rs

const_primes/cache/
prime_factors.rs
