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