const_primes/cache/
prime_factors.rs

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

const_primes/cache/
prime_factors.rs
