const_primes/cache/
mod.rs

1//! This module contains the implementation of the type [`Primes`] (and related iterators),
2//! which functions as a cache of prime numbers for related computations.
3
4mod prime_factors;
5mod primes_into_iter;
6mod primes_iter;
7
8pub use prime_factors::{PrimeFactorization, PrimeFactors};
9pub use primes_into_iter::PrimesIntoIter;
10pub use primes_iter::PrimesIter;
11
12use crate::{primes, Underlying};
13
14// region: Primes<N>
15
16/// A wrapper around an array that consists of the first `N` primes.
17/// Can use those primes for related computations.
18/// Ensures that `N` is non-zero at compile time.
19///
20/// # Examples
21///
22/// Basic usage:
23///
24/// ```
25/// # use const_primes::Primes;
26/// const PRIMES: Primes<3> = Primes::new();
27/// assert_eq!(PRIMES[2], 5);
28/// assert_eq!(PRIMES.as_array(), &[2, 3, 5]);
29/// ```
30///
31/// Reuse sieved primes for other computations:
32///
33/// ```
34/// # use const_primes::Primes;
35/// const CACHE: Primes<100> = Primes::new();
36/// const PRIME_CHECK: Option<bool> = CACHE.is_prime(541);
37/// const PRIME_COUNT: Option<usize> = CACHE.prime_pi(200);
38///
39/// assert_eq!(PRIME_CHECK, Some(true));
40/// assert_eq!(PRIME_COUNT, Some(46));
41///
42/// // If questions are asked about numbers outside the cache it returns None
43/// assert_eq!(CACHE.is_prime(1000), None);
44/// assert_eq!(CACHE.prime_pi(1000), None);
45/// ```
46#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
47#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
48#[cfg_attr(
49    feature = "zerocopy",
50    derive(zerocopy::IntoBytes, zerocopy::Immutable, zerocopy::KnownLayout)
51)]
52#[cfg_attr(
53    feature = "rkyv",
54    derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)
55)]
56#[cfg_attr(feature = "zerocopy", repr(transparent))]
57pub struct Primes<const N: usize>(
58    #[cfg_attr(feature = "serde", serde(with = "serde_arrays"))] [Underlying; N],
59);
60
61impl<const N: usize> Primes<N> {
62    /// Generates a new instance that contains the first `N` primes.
63    ///
64    /// Uses a [segmented sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve).
65    ///
66    /// # Examples
67    ///
68    /// Basic usage:
69    ///
70    /// ```
71    /// # use const_primes::Primes;
72    /// const PRIMES: Primes<3> = Primes::new();
73    /// assert_eq!(PRIMES.as_array(), &[2, 3, 5]);
74    /// ```
75    ///
76    /// Determine `N` through type inference
77    ///
78    /// ```
79    /// # use const_primes::Primes;
80    /// assert_eq!(Primes::new().as_array(), &[2, 3, 5, 7, 11]);
81    /// ```
82    ///
83    /// Specify `N` manually
84    ///
85    /// ```
86    /// # use const_primes::Primes;
87    /// let primes = Primes::<5>::new();
88    /// assert_eq!(primes.as_array(), &[2, 3, 5, 7, 11]);
89    /// ```
90    ///
91    /// # Errors
92    ///
93    /// It is a compile error to use an `N` of 0.
94    ///
95    /// ```compile_fail
96    /// # use const_primes::Primes;
97    /// const NO_PRIMES: Primes<0> = Primes::new();
98    /// ```
99    #[must_use = "the associated method only returns a new value"]
100    pub const fn new() -> Self {
101        const { assert!(N > 0, "`N` must be at least 1") }
102        Self(primes())
103    }
104
105    /// Returns whether `n` is prime, if it is smaller than or equal to the largest prime in `self`.
106    ///
107    /// Uses a binary search.
108    ///
109    /// # Example
110    ///
111    /// Basic usage:
112    ///
113    /// ```
114    /// # use const_primes::Primes;
115    /// const PRIMES: Primes<100> = Primes::new();
116    /// const TMOLTUAE: Option<bool> = PRIMES.is_prime(42);
117    ///
118    /// assert_eq!(PRIMES.is_prime(13), Some(true));
119    /// assert_eq!(TMOLTUAE, Some(false));
120    /// // 1000 is larger than 541, the largest prime in the cache,
121    /// // so we don't know whether it's prime.
122    /// assert_eq!(PRIMES.is_prime(1000), None);
123    /// ```
124    #[must_use = "the method only returns a new value and does not modify `self`"]
125    pub const fn is_prime(&self, n: u32) -> Option<bool> {
126        match self.binary_search(n) {
127            Ok(_) => Some(true),
128            Err(i) => {
129                if i < N {
130                    Some(false)
131                } else {
132                    None
133                }
134            }
135        }
136    }
137
138    /// Returns the number of primes smaller than or equal to `n`, if it's smaller than or equal to the largest prime in `self`.
139    ///
140    /// Uses a binary search to count the primes.
141    ///
142    /// # Example
143    ///
144    /// Basic usage:
145    ///
146    /// ```
147    /// # use const_primes::Primes;
148    /// const CACHE: Primes<100> = Primes::new();
149    /// const COUNT1: Option<usize> = CACHE.prime_pi(500);
150    /// const COUNT2: Option<usize> = CACHE.prime_pi(11);
151    /// const OUT_OF_BOUNDS: Option<usize> = CACHE.prime_pi(1_000);
152    ///
153    /// assert_eq!(COUNT1, Some(95));
154    /// assert_eq!(COUNT2, Some(5));
155    /// assert_eq!(OUT_OF_BOUNDS, None);
156    /// ```
157    #[must_use = "the method only returns a new value and does not modify `self`"]
158    pub const fn prime_pi(&self, n: Underlying) -> Option<usize> {
159        match self.binary_search(n) {
160            Ok(i) => Some(i + 1),
161            Err(maybe_i) => {
162                if maybe_i < N {
163                    Some(maybe_i)
164                } else {
165                    None
166                }
167            }
168        }
169    }
170
171    /// Returns an iterator over the prime factors of the given number in increasing order as well as their
172    /// multiplicities.
173    ///
174    /// If a number contains prime factors larger than the largest prime in `self`,
175    /// they will not be yielded by the iterator, but their product can be retrieved by calling
176    /// [`remainder`](PrimeFactorization::remainder) on the iterator.
177    ///
178    /// If you do not need to know the multiplicity of each prime factor,
179    /// it may be faster to use [`prime_factors`](Self::prime_factors).
180    ///
181    /// # Examples
182    ///
183    /// Basic usage:
184    ///
185    /// ```
186    /// # use const_primes::Primes;
187    /// // Contains the primes [2, 3, 5]
188    /// const CACHE: Primes<3> = Primes::new();
189    ///
190    /// assert_eq!(CACHE.prime_factorization(15).collect::<Vec<_>>(), &[(3, 1), (5, 1)]);
191    /// ```
192    ///
193    /// The second element of the returned tuples is the multiplicity of the prime in the number:
194    ///
195    /// ```
196    /// # use const_primes::Primes;
197    /// # const CACHE: Primes<3> = Primes::new();
198    /// // 1024 = 2^10
199    /// assert_eq!(CACHE.prime_factorization(1024).next(), Some((2, 10)));
200    /// ```
201    ///
202    /// 294 has 7 as a prime factor, but 7 is not in the cache:
203    ///
204    /// ```
205    /// # use const_primes::Primes;
206    /// # const CACHE: Primes<3> = Primes::new();
207    /// // 294 = 2*3*7*7
208    /// let mut factorization_of_294 = CACHE.prime_factorization(294);
209    ///
210    /// // only 2 and 3 are in the cache:
211    /// assert_eq!(factorization_of_294.by_ref().collect::<Vec<_>>(), &[(2, 1), (3, 1)]);
212    ///
213    /// // the factor of 7*7 can be found with the remainder function:
214    /// assert_eq!(factorization_of_294.remainder(), Some(49));
215    /// ```
216    #[inline]
217    pub fn prime_factorization(&self, number: Underlying) -> PrimeFactorization<'_> {
218        PrimeFactorization::new(&self.0, number)
219    }
220
221    /// Returns an iterator over all the prime factors of the given number in increasing order.
222    ///
223    /// If a number contains prime factors larger than the largest prime in `self`,
224    /// they will not be yielded by the iterator, but their product can be retrieved by calling
225    /// [`remainder`](PrimeFactors::remainder) on the iterator.
226    ///
227    /// If you also wish to know the multiplicity of each prime factor of the number,
228    /// take a look at [`prime_factorization`](Self::prime_factorization).
229    ///
230    /// # Examples
231    ///
232    /// ```
233    /// # use const_primes::Primes;
234    /// // Contains [2, 3, 5]
235    /// const CACHE: Primes<3> = Primes::new();
236    ///
237    /// assert_eq!(CACHE.prime_factors(3*5).collect::<Vec<_>>(), &[3, 5]);
238    /// assert_eq!(CACHE.prime_factors(2*2*2*2*3).collect::<Vec<_>>(), &[2, 3]);
239    /// ```
240    ///
241    /// 294 has 7 as a prime factor, but 7 is not in the cache:
242    ///
243    /// ```
244    /// # use const_primes::Primes;
245    /// # const CACHE: Primes<3> = Primes::new();
246    /// // 294 = 2*3*7*7
247    /// let mut factors_of_294 = CACHE.prime_factors(294);
248    ///
249    /// // only 2 and 3 are in the cache
250    /// assert_eq!(factors_of_294.by_ref().collect::<Vec<_>>(), &[2, 3]);
251    ///
252    /// // the factor of 7*7 can be found with the remainder function
253    /// assert_eq!(factors_of_294.remainder(), Some(49));
254    /// ```
255    #[inline]
256    pub fn prime_factors(&self, number: Underlying) -> PrimeFactors<'_> {
257        PrimeFactors::new(&self.0, number)
258    }
259
260    // region: Next prime
261
262    /// Returns the largest prime less than `n`.  
263    /// If `n` is 0, 1, 2, or larger than the largest prime in `self` this returns `None`.
264    ///
265    /// Uses a binary search.
266    ///
267    /// # Example
268    ///
269    /// ```
270    /// # use const_primes::Primes;
271    /// const CACHE: Primes<100> = Primes::new();
272    /// const PREV400: Option<u32> = CACHE.previous_prime(400);
273    /// assert_eq!(PREV400, Some(397));
274    /// ```
275    #[must_use = "the method only returns a new value and does not modify `self`"]
276    pub const fn previous_prime(&self, n: Underlying) -> Option<Underlying> {
277        if n <= 2 {
278            None
279        } else {
280            match self.binary_search(n) {
281                Ok(i) | Err(i) => {
282                    if i > 0 && i < N {
283                        Some(self.0[i - 1])
284                    } else {
285                        None
286                    }
287                }
288            }
289        }
290    }
291
292    /// Returns the smallest prime greater than `n`.  
293    /// If `n` is larger than or equal to the largest prime in `self` this returns `None`.
294    ///
295    /// Uses a binary search.
296    ///
297    /// # Example
298    ///
299    /// ```
300    /// # use const_primes::Primes;
301    /// const CACHE: Primes<100> = Primes::new();
302    /// const NEXT: Option<u32> = CACHE.next_prime(400);
303    /// assert_eq!(NEXT, Some(401));
304    /// ```
305    #[must_use = "the method only returns a new value and does not modify `self`"]
306    pub const fn next_prime(&self, n: Underlying) -> Option<Underlying> {
307        match self.binary_search(n) {
308            Ok(i) => {
309                if i + 1 < self.len() {
310                    Some(self.0[i + 1])
311                } else {
312                    None
313                }
314            }
315            Err(i) => {
316                if i < N {
317                    Some(self.0[i])
318                } else {
319                    None
320                }
321            }
322        }
323    }
324
325    // endregion: Next prime
326
327    /// Searches the underlying array of primes for the target integer.
328    ///
329    /// If the target is found it returns a [`Result::Ok`] that contains the index of the matching element.
330    /// If the target is not found in the array a [`Result::Err`] is returned that indicates where the
331    /// target could be inserted into the array while maintaining the sorted order.
332    ///
333    /// # Example
334    ///
335    /// Basic usage:
336    ///
337    /// ```
338    /// # use const_primes::Primes;
339    /// // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
340    /// const PRIMES: Primes<10> = Primes::new();
341    ///
342    /// const WHERE_29: Result<usize, usize> = PRIMES.binary_search(29);
343    /// const WHERE_6: Result<usize, usize> = PRIMES.binary_search(6);
344    /// const WHERE_1000: Result<usize, usize> = PRIMES.binary_search(1_000);
345    ///
346    /// assert_eq!(WHERE_29, Ok(9));
347    /// assert_eq!(WHERE_6, Err(3));
348    /// assert_eq!(WHERE_1000, Err(10));
349    /// ```
350    #[must_use = "the method only returns a new value and does not modify `self`"]
351    pub const fn binary_search(&self, target: Underlying) -> Result<usize, usize> {
352        let mut size = N;
353        let mut left = 0;
354        let mut right = size;
355        while left < right {
356            let mid = left + size / 2;
357            let candidate = self.0[mid];
358            if candidate < target {
359                left = mid + 1;
360            } else if candidate > target {
361                right = mid;
362            } else {
363                return Ok(mid);
364            }
365            size = right - left;
366        }
367        Err(left)
368    }
369
370    // region: Conversions
371
372    /// Converts `self` into an array of size `N`.
373    ///
374    /// # Example
375    ///
376    /// Basic usage:
377    ///
378    /// ```
379    /// # use const_primes::Primes;
380    /// const PRIMES: [u32; 5] = Primes::new().into_array();
381    /// assert_eq!(PRIMES, [2, 3, 5, 7, 11]);
382    /// ```
383    #[inline]
384    #[must_use = "the method only returns a new value and does not modify `self`"]
385    pub const fn into_array(self) -> [Underlying; N] {
386        self.0
387    }
388
389    /// Returns a reference to the underlying array.
390    #[inline]
391    #[must_use = "the method only returns a new value and does not modify `self`"]
392    pub const fn as_array(&self) -> &[Underlying; N] {
393        &self.0
394    }
395
396    /// Returns a slice that contains the entire underlying array.
397    #[inline]
398    #[must_use = "the method only returns a new value and does not modify `self`"]
399    pub const fn as_slice(&self) -> &[Underlying] {
400        self.0.as_slice()
401    }
402
403    /// Returns a borrowing iterator over the primes.
404    ///
405    /// # Example
406    ///
407    /// Basic usage:
408    ///
409    /// ```
410    /// # use const_primes::Primes;
411    /// const PRIMES: Primes<10> = Primes::new();
412    ///
413    /// let mut primes = PRIMES.iter();
414    ///
415    /// assert_eq!(primes.nth(5), Some(&13));
416    /// assert_eq!(primes.next(), Some(&17));
417    /// assert_eq!(primes.as_slice(), &[19, 23, 29]);
418    /// ```
419    #[inline]
420    pub fn iter(&self) -> PrimesIter<'_> {
421        PrimesIter::new(IntoIterator::into_iter(&self.0))
422    }
423
424    // endregion: Conversions
425
426    /// Returns a reference to the element at the given index if it is within bounds.
427    ///
428    /// # Example
429    ///
430    /// Basic usage:
431    ///
432    /// ```
433    /// # use const_primes::Primes;
434    /// const PRIMES: Primes<5> = Primes::new();
435    /// const THIRD_PRIME: Option<&u32> = PRIMES.get(2);
436    /// assert_eq!(THIRD_PRIME, Some(&5));
437    /// ```
438    #[inline]
439    #[must_use = "the method only returns a new value and does not modify `self`"]
440    pub const fn get(&self, index: usize) -> Option<&Underlying> {
441        if index < N {
442            Some(&self.0[index])
443        } else {
444            None
445        }
446    }
447
448    /// Returns a reference to the last prime in `self`. This is also the largest prime in `self`.
449    ///
450    /// # Example
451    ///
452    /// Basic usage:
453    ///
454    /// ```
455    /// # use const_primes::Primes;
456    /// const PRIMES: Primes<5> = Primes::new();
457    /// assert_eq!(PRIMES.last(), &11);
458    /// ```
459    #[inline]
460    #[must_use = "the method only returns a new value and does not modify `self`"]
461    pub const fn last(&self) -> &Underlying {
462        match self.0.last() {
463            Some(l) => l,
464            None => panic!("unreachable: an empty `Primes<N>` can not be created"),
465        }
466    }
467
468    /// Returns the number of primes in `self`.
469    ///
470    /// # Example
471    ///
472    /// Basic usage:
473    ///
474    /// ```
475    /// # use const_primes::Primes;
476    /// const PRIMES: Primes<5> = Primes::new();
477    /// assert_eq!(PRIMES.len(), 5);
478    /// ```
479    #[inline]
480    #[must_use = "the method only returns a new value and does not modify `self`"]
481    // Can never be empty since we panic if the user tries to create an empty `Primes`.
482    #[allow(clippy::len_without_is_empty)]
483    pub const fn len(&self) -> usize {
484        N
485    }
486
487    /// Returns the value of the Euler totient function of `n`:
488    /// the number of positive integers up to `n` that are relatively prime to it.
489    ///
490    /// # Example
491    ///
492    /// ```
493    /// # use const_primes::{Primes, cache::PartialTotient};
494    /// const CACHE: Primes<3> = Primes::new();
495    /// const TOTIENT_OF_6: Result<u32, PartialTotient> = CACHE.totient(2*3);
496    ///
497    /// assert_eq!(TOTIENT_OF_6, Ok(2));
498    /// ```
499    ///
500    /// # Errors
501    ///
502    /// The totient function is computed here as the product over all factors of the form p^(k-1)*(p-1) where
503    /// p is the primes in the prime factorization of `n` and k is their multiplicity.
504    /// If `n` contains prime factors that are not part of `self`, a [`Result::Err`] is returned
505    /// that contains a [`PartialTotient`] struct that contains the result from using only the primes in `self`,
506    /// as well as the product of the prime factors that are not included in `self`.
507    ///
508    /// # Error example
509    ///
510    /// The number 2450 is equal to 2\*5\*5\*7\*7.
511    /// If the cache does not contain 7 the function runs out of primes after 5,
512    /// and can not finish the computation:
513    ///
514    /// ```
515    /// # use const_primes::{Primes, cache::PartialTotient};
516    /// // Contains the primes [2, 3, 5]
517    /// const CACHE: Primes<3> = Primes::new();
518    /// const TOTIENT_OF_2450: Result<u32, PartialTotient> = CACHE.totient(2*5*5*7*7);
519    ///
520    /// assert_eq!(
521    ///     TOTIENT_OF_2450,
522    ///     Err( PartialTotient {
523    /// //                 totient(2*5*5) = 20
524    ///         totient_using_known_primes: 20,
525    ///         product_of_unknown_prime_factors: 49
526    ///     })
527    /// );
528    /// ```
529    pub const fn totient(&self, mut n: Underlying) -> Result<Underlying, PartialTotient> {
530        if n == 0 {
531            return Ok(0);
532        }
533
534        let mut i = 0;
535        let mut ans = 1;
536        while let Some(&prime) = self.get(i) {
537            let mut count = 0;
538            while n % prime == 0 {
539                n /= prime;
540                count += 1;
541            }
542
543            if count > 0 {
544                ans *= prime.pow(count - 1) * (prime - 1);
545            }
546
547            if n == 1 {
548                break;
549            }
550            i += 1;
551        }
552
553        if n == 1 {
554            Ok(ans)
555        } else {
556            Err(PartialTotient {
557                totient_using_known_primes: ans,
558                product_of_unknown_prime_factors: n,
559            })
560        }
561    }
562}
563
564/// Contains the result of a partially successful evaluation of the [`totient`](Primes::totient) function.
565#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
566#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
567#[cfg_attr(
568    feature = "rkyv",
569    derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)
570)]
571pub struct PartialTotient {
572    /// The result of computing the totient function with only the primes in the related [`Primes`] struct.
573    pub totient_using_known_primes: Underlying,
574    /// The product of all remaining prime factors of the number.
575    pub product_of_unknown_prime_factors: Underlying,
576}
577
578impl<const N: usize> Default for Primes<N> {
579    /// It is a compile error if `N` is 0.
580    fn default() -> Self {
581        const { assert!(N > 0, "`N` must be at least 1") }
582        Self(primes())
583    }
584}
585
586impl<const N: usize, I> core::ops::Index<I> for Primes<N>
587where
588    I: core::slice::SliceIndex<[Underlying]>,
589{
590    type Output = I::Output;
591    #[inline]
592    fn index(&self, index: I) -> &Self::Output {
593        self.0.index(index)
594    }
595}
596
597impl<const N: usize> From<Primes<N>> for [Underlying; N] {
598    #[inline]
599    fn from(const_primes: Primes<N>) -> Self {
600        const_primes.0
601    }
602}
603
604// region: AsRef
605
606impl<const N: usize> AsRef<[Underlying]> for Primes<N> {
607    #[inline]
608    fn as_ref(&self) -> &[Underlying] {
609        &self.0
610    }
611}
612
613impl<const N: usize> AsRef<[Underlying; N]> for Primes<N> {
614    #[inline]
615    fn as_ref(&self) -> &[Underlying; N] {
616        &self.0
617    }
618}
619
620// endregion: AsRef
621
622// region: IntoIterator
623
624impl<const N: usize> IntoIterator for Primes<N> {
625    type Item = Underlying;
626    type IntoIter = PrimesIntoIter<N>;
627    #[inline]
628    fn into_iter(self) -> Self::IntoIter {
629        PrimesIntoIter::new(self.0.into_iter())
630    }
631}
632
633impl<'a, const N: usize> IntoIterator for &'a Primes<N> {
634    type IntoIter = PrimesIter<'a>;
635    type Item = &'a Underlying;
636    fn into_iter(self) -> Self::IntoIter {
637        PrimesIter::new(IntoIterator::into_iter(&self.0))
638    }
639}
640
641// endregion: IntoIterator
642
643// endregion: Primes<N>
644
645#[cfg(test)]
646mod test {
647    use crate::next_prime;
648
649    use super::*;
650
651    // region: TraitImpls
652
653    #[test]
654    fn verify_impl_from_primes_traits() {
655        const N: usize = 10;
656        const P: Primes<N> = Primes::new();
657        let p: [Underlying; N] = P.into();
658        assert_eq!(p, P.as_ref());
659        assert_eq!(
660            P.as_array(),
661            <Primes<N> as AsRef<[Underlying; N]>>::as_ref(&P)
662        );
663    }
664
665    #[test]
666    fn check_into_iter() {
667        const P: Primes<10> = Primes::new();
668        for (i, prime) in P.into_iter().enumerate() {
669            assert_eq!(prime, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29][i]);
670        }
671    }
672
673    // endregion: TraitImpls
674
675    #[test]
676    fn check_binary_search() {
677        const CACHE: Primes<100> = Primes::new();
678        type BSResult = Result<usize, usize>;
679        const FOUND2: BSResult = CACHE.binary_search(2);
680        const INSERT0: BSResult = CACHE.binary_search(0);
681        const INSERT4: BSResult = CACHE.binary_search(4);
682        const FOUND541: BSResult = CACHE.binary_search(541);
683        const NOINFO542: BSResult = CACHE.binary_search(542);
684        const BIG: BSResult = CACHE.binary_search(1000000);
685        assert_eq!(FOUND2, Ok(0));
686        assert_eq!(INSERT0, Err(0));
687        assert_eq!(INSERT4, Err(2));
688        assert_eq!(FOUND541, Ok(99));
689        assert_eq!(NOINFO542, Err(100));
690        assert_eq!(BIG, Err(100));
691    }
692
693    #[test]
694    fn test_into_iter() {
695        const PRIMES: Primes<10> = Primes::new();
696
697        for (&prime, ans) in (&PRIMES)
698            .into_iter()
699            .zip([2, 3, 5, 7, 11, 13, 17, 19, 23, 29])
700        {
701            assert_eq!(prime, ans);
702        }
703    }
704
705    #[test]
706    fn check_previous_prime() {
707        const CACHE: Primes<100> = Primes::new();
708        const PREV0: Option<Underlying> = CACHE.previous_prime(0);
709        const PREV400: Option<Underlying> = CACHE.previous_prime(400);
710        const PREV541: Option<Underlying> = CACHE.previous_prime(541);
711        const PREV542: Option<Underlying> = CACHE.previous_prime(542);
712        const PREVS: [Underlying; 18] = [
713            2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11, 13, 13, 13, 13, 17, 17, 19,
714        ];
715        for (i, prev) in PREVS.into_iter().enumerate() {
716            assert_eq!(Some(prev), CACHE.previous_prime(i as u32 + 3));
717        }
718        assert_eq!(PREV0, None);
719        assert_eq!(PREV400, Some(397));
720        assert_eq!(PREV541, Some(523));
721        assert_eq!(PREV542, None);
722    }
723
724    #[test]
725    fn check_prime_factorization() {
726        const CACHE: Primes<3> = Primes::new();
727
728        let mut factorization_of_14 = CACHE.prime_factorization(14);
729
730        assert_eq!(factorization_of_14.next(), Some((2, 1)));
731        assert_eq!(factorization_of_14.next(), None);
732        assert_eq!(factorization_of_14.remainder(), Some(7));
733
734        let mut factorization_of_15 = CACHE.prime_factorization(15);
735
736        assert_eq!(factorization_of_15.next(), Some((3, 1)));
737        assert_eq!(factorization_of_15.next(), Some((5, 1)));
738        assert!(factorization_of_15.remainder().is_none());
739
740        let mut factorization_of_270 = CACHE.prime_factorization(2 * 3 * 3 * 3 * 5);
741        assert_eq!(factorization_of_270.next(), Some((2, 1)));
742        assert_eq!(factorization_of_270.next(), Some((3, 3)));
743        assert_eq!(factorization_of_270.next(), Some((5, 1)));
744    }
745
746    #[test]
747    fn check_prime_factors() {
748        const CACHE: Primes<3> = Primes::new();
749
750        let mut factors_of_14 = CACHE.prime_factors(14);
751
752        assert_eq!(factors_of_14.next(), Some(2));
753        assert_eq!(factors_of_14.next(), None);
754        assert_eq!(factors_of_14.remainder(), Some(7));
755
756        let mut factors_of_15 = CACHE.prime_factors(15);
757        assert_eq!(factors_of_15.next(), Some(3));
758        assert_eq!(factors_of_15.next(), Some(5));
759        assert!(factors_of_15.remainder().is_none());
760
761        let mut factors_of_270 = CACHE.prime_factors(2 * 3 * 3 * 3 * 5);
762        assert_eq!(factors_of_270.next(), Some(2));
763        assert_eq!(factors_of_270.next(), Some(3));
764        assert_eq!(factors_of_270.next(), Some(5));
765    }
766
767    #[test]
768    fn check_next_prime() {
769        const CACHE: Primes<100> = Primes::new();
770        const SPGEQ0: Option<Underlying> = CACHE.next_prime(0);
771        const SPGEQ400: Option<Underlying> = CACHE.next_prime(400);
772        const SPGEQ541: Option<Underlying> = CACHE.next_prime(540);
773        const SPGEQ542: Option<Underlying> = CACHE.next_prime(541);
774        assert_eq!(SPGEQ0, Some(2));
775        assert_eq!(SPGEQ400, Some(401));
776        assert_eq!(SPGEQ541, Some(541));
777        assert_eq!(SPGEQ542, None);
778
779        const N: usize = 31;
780        const NEXT_PRIME: [u32; N] = [
781            2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13, 17, 17, 17, 17, 19, 19, 23, 23, 23, 23,
782            29, 29, 29, 29, 29, 29, 31, 31,
783        ];
784        const P: Primes<N> = Primes::new();
785
786        for (n, next) in NEXT_PRIME.iter().enumerate().take(N) {
787            assert_eq!(P.next_prime(n as u32), Some(*next));
788        }
789    }
790
791    #[test]
792    fn verify_into_array() {
793        const N: usize = 10;
794        const P: Primes<N> = Primes::new();
795        const A: [Underlying; N] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
796        assert_eq!(P.into_array(), A);
797    }
798
799    #[test]
800    fn verify_as_slice() {
801        const N: usize = 10;
802        const P: Primes<N> = Primes::new();
803        const A: [Underlying; N] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
804        assert_eq!(P.as_slice(), &A);
805    }
806
807    #[test]
808    fn verify_as_array() {
809        const N: usize = 10;
810        const P: Primes<N> = Primes::new();
811        const A: [Underlying; N] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
812        assert_eq!(P.as_array(), &A);
813    }
814
815    #[test]
816    fn check_get() {
817        const N: usize = 10;
818        const P: Primes<N> = Primes::new();
819        const A: [Underlying; N] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
820        for (n, gotten) in A.iter().enumerate().take(N) {
821            assert_eq!(P.get(n), Some(gotten));
822        }
823        for n in N + 1..2 * N {
824            assert!(P.get(n).is_none());
825        }
826    }
827
828    #[test]
829    fn check_last_and_len() {
830        const PRIMES: [Underlying; 10] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
831        macro_rules! check_last_n {
832            ($($n:literal),+) => {
833                $(
834                    {
835                        let p: Primes<$n> = Primes::new();
836                        assert_eq!(*p.last(), PRIMES[$n - 1]);
837                        assert_eq!(p.len(), $n);
838                        assert_eq!(*p.last(), p[$n - 1]);
839                    }
840                )+
841            };
842        }
843        check_last_n!(1, 2, 3, 4, 5, 6, 7, 8, 9);
844    }
845
846    #[test]
847    fn check_count_primes_leq() {
848        const N: usize = 79;
849        const PRIME_COUNTS: [usize; N] = [
850            0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9,
851            10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
852            15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20,
853            21, 21, 21, 21, 21, 21,
854        ];
855        const P: Primes<N> = Primes::new();
856
857        for (n, count) in PRIME_COUNTS.iter().enumerate().take(N) {
858            assert_eq!(P.prime_pi(n as u32), Some(*count));
859        }
860
861        for n in *P.last() + 1..*P.last() * 2 {
862            assert!(P.prime_pi(n).is_none());
863        }
864    }
865
866    #[test]
867    fn check_iter() {
868        const P: Primes<10> = Primes::new();
869        for (p1, p2) in P.iter().zip([2, 3, 5, 7, 11, 13, 17, 19, 23, 29].iter()) {
870            assert_eq!(p1, p2);
871        }
872    }
873
874    #[test]
875    fn check_totient() {
876        const TOTIENTS: [Underlying; 101] = [
877            0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20,
878            12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46,
879            16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44,
880            24, 70, 24, 72, 36, 40, 36, 60, 24, 78, 32, 54, 40, 82, 24, 64, 42, 56, 40, 88, 24, 72,
881            44, 60, 46, 72, 32, 96, 42, 60, 40,
882        ];
883        const NEXT_OUTSIDE: Underlying = match next_prime(*BIG_CACHE.last() as u64) {
884            Some(np) => np as Underlying,
885            None => panic!(),
886        };
887
888        const SMALL_CACHE: Primes<3> = Primes::new();
889        const BIG_CACHE: Primes<100> = Primes::new();
890
891        assert_eq!(SMALL_CACHE.totient(6), Ok(2));
892        assert_eq!(
893            SMALL_CACHE.totient(2 * 5 * 5 * 7 * 7),
894            Err(PartialTotient {
895                totient_using_known_primes: 20,
896                product_of_unknown_prime_factors: 49
897            })
898        );
899
900        for (i, totient) in TOTIENTS.into_iter().enumerate() {
901            assert_eq!(BIG_CACHE.totient(i as Underlying), Ok(totient));
902            if i != 0 {
903                assert_eq!(
904                    BIG_CACHE.totient((i as Underlying) * NEXT_OUTSIDE),
905                    Err(PartialTotient {
906                        totient_using_known_primes: totient,
907                        product_of_unknown_prime_factors: NEXT_OUTSIDE
908                    })
909                );
910            }
911        }
912    }
913
914    #[cfg(feature = "zerocopy")]
915    #[test]
916    fn test_as_bytes() {
917        use zerocopy::IntoBytes;
918        const P: Primes<3> = Primes::new();
919        assert_eq!(P.as_bytes(), &[2, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0]);
920    }
921
922    #[cfg(feature = "serde")]
923    #[test]
924    fn test_serde() {
925        const P: Primes<3> = Primes::new();
926        const STRING_VERSION: &str = "[2,3,5]";
927        assert_eq!(serde_json::to_string(&P).unwrap(), STRING_VERSION);
928        assert_eq!(P, serde_json::from_str(STRING_VERSION).unwrap());
929    }
930}
const_primes/cache/mod.rs

const_primes/cache/
mod.rs
