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