Struct Primes

pub struct Primes<const N: usize>(/* private fields */);

A wrapper around an array that consists of the first N primes. Can use those primes for related computations. Ensures that N is non-zero at compile time.

Examples

Basic usage:

const PRIMES: Primes<3> = Primes::new();
assert_eq!(PRIMES[2], 5);
assert_eq!(PRIMES.as_array(), &[2, 3, 5]);

Reuse sieved primes for other computations:

const CACHE: Primes<100> = Primes::new();
const PRIME_CHECK: Option<bool> = CACHE.is_prime(541);
const PRIME_COUNT: Option<usize> = CACHE.prime_pi(200);

assert_eq!(PRIME_CHECK, Some(true));
assert_eq!(PRIME_COUNT, Some(46));

// If questions are asked about numbers outside the cache it returns None
assert_eq!(CACHE.is_prime(1000), None);
assert_eq!(CACHE.prime_pi(1000), None);

Implementations

impl<const N: usize> Primes<N>

pub const fn new() -> Self

Generates a new instance that contains the first N primes.

Uses a segmented sieve of Eratosthenes.

Examples

Basic usage:

const PRIMES: Primes<3> = Primes::new();
assert_eq!(PRIMES.as_array(), &[2, 3, 5]);

Determine N through type inference

assert_eq!(Primes::new().as_array(), &[2, 3, 5, 7, 11]);

Specify N manually

let primes = Primes::<5>::new();
assert_eq!(primes.as_array(), &[2, 3, 5, 7, 11]);

Errors

It is a compile error to use an N of 0.

const NO_PRIMES: Primes<0> = Primes::new();

pub const fn is_prime(&self, n: u32) -> Option<bool>

Returns whether n is prime, if it is smaller than or equal to the largest prime in self.

Uses a binary search.

Example

Basic usage:

const PRIMES: Primes<100> = Primes::new();
const TMOLTUAE: Option<bool> = PRIMES.is_prime(42);

assert_eq!(PRIMES.is_prime(13), Some(true));
assert_eq!(TMOLTUAE, Some(false));
// 1000 is larger than 541, the largest prime in the cache,
// so we don't know whether it's prime.
assert_eq!(PRIMES.is_prime(1000), None);

pub const fn prime_pi(&self, n: u32) -> Option<usize>

Returns the number of primes smaller than or equal to n, if it’s smaller than or equal to the largest prime in self.

Uses a binary search to count the primes.

Example

Basic usage:

const CACHE: Primes<100> = Primes::new();
const COUNT1: Option<usize> = CACHE.prime_pi(500);
const COUNT2: Option<usize> = CACHE.prime_pi(11);
const OUT_OF_BOUNDS: Option<usize> = CACHE.prime_pi(1_000);

assert_eq!(COUNT1, Some(95));
assert_eq!(COUNT2, Some(5));
assert_eq!(OUT_OF_BOUNDS, None);

pub fn prime_factorization(&self, number: u32) -> PrimeFactorization<'_>

Returns an iterator over the prime factors of the given number in increasing order as well as their multiplicities.

If a number contains prime factors larger than the largest prime in self, they will not be yielded by the iterator, but their product can be retrieved by calling remainder on the iterator.

If you do not need to know the multiplicity of each prime factor, it may be faster to use prime_factors.

Examples

Basic usage:

// Contains the primes [2, 3, 5]
const CACHE: Primes<3> = Primes::new();

assert_eq!(CACHE.prime_factorization(15).collect::<Vec<_>>(), &[(3, 1), (5, 1)]);

The second element of the returned tuples is the multiplicity of the prime in the number:

// 1024 = 2^10
assert_eq!(CACHE.prime_factorization(1024).next(), Some((2, 10)));

294 has 7 as a prime factor, but 7 is not in the cache:

// 294 = 2*3*7*7
let mut factorization_of_294 = CACHE.prime_factorization(294);

// only 2 and 3 are in the cache:
assert_eq!(factorization_of_294.by_ref().collect::<Vec<_>>(), &[(2, 1), (3, 1)]);

// the factor of 7*7 can be found with the remainder function:
assert_eq!(factorization_of_294.remainder(), Some(49));

pub fn prime_factors(&self, number: u32) -> PrimeFactors<'_>

Returns an iterator over all the prime factors of the given number in increasing order.

If a number contains prime factors larger than the largest prime in self, they will not be yielded by the iterator, but their product can be retrieved by calling remainder on the iterator.

If you also wish to know the multiplicity of each prime factor of the number, take a look at prime_factorization.

Examples

// Contains [2, 3, 5]
const CACHE: Primes<3> = Primes::new();

assert_eq!(CACHE.prime_factors(3*5).collect::<Vec<_>>(), &[3, 5]);
assert_eq!(CACHE.prime_factors(2*2*2*2*3).collect::<Vec<_>>(), &[2, 3]);

294 has 7 as a prime factor, but 7 is not in the cache:

// 294 = 2*3*7*7
let mut factors_of_294 = CACHE.prime_factors(294);

// only 2 and 3 are in the cache
assert_eq!(factors_of_294.by_ref().collect::<Vec<_>>(), &[2, 3]);

// the factor of 7*7 can be found with the remainder function
assert_eq!(factors_of_294.remainder(), Some(49));

pub const fn previous_prime(&self, n: u32) -> Option<u32>

Returns the largest prime less than n.
If n is 0, 1, 2, or larger than the largest prime in self this returns None.

Uses a binary search.

Example

const CACHE: Primes<100> = Primes::new();
const PREV400: Option<u32> = CACHE.previous_prime(400);
assert_eq!(PREV400, Some(397));

pub const fn next_prime(&self, n: u32) -> Option<u32>

Returns the smallest prime greater than n.
If n is larger than or equal to the largest prime in self this returns None.

Uses a binary search.

Example

const CACHE: Primes<100> = Primes::new();
const NEXT: Option<u32> = CACHE.next_prime(400);
assert_eq!(NEXT, Some(401));

pub const fn binary_search(&self, target: u32) -> Result<usize, usize>

Searches the underlying array of primes for the target integer.

If the target is found it returns a Result::Ok that contains the index of the matching element. If the target is not found in the array a Result::Err is returned that indicates where the target could be inserted into the array while maintaining the sorted order.

Example

Basic usage:

// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
const PRIMES: Primes<10> = Primes::new();

const WHERE_29: Result<usize, usize> = PRIMES.binary_search(29);
const WHERE_6: Result<usize, usize> = PRIMES.binary_search(6);
const WHERE_1000: Result<usize, usize> = PRIMES.binary_search(1_000);

assert_eq!(WHERE_29, Ok(9));
assert_eq!(WHERE_6, Err(3));
assert_eq!(WHERE_1000, Err(10));

pub const fn into_array(self) -> [u32; N]

Converts self into an array of size N.

Example

Basic usage:

const PRIMES: [u32; 5] = Primes::new().into_array();
assert_eq!(PRIMES, [2, 3, 5, 7, 11]);

pub const fn as_array(&self) -> &[u32; N]

Returns a reference to the underlying array.

pub const fn as_slice(&self) -> &[u32]

Returns a slice that contains the entire underlying array.

pub fn iter(&self) -> PrimesIter<'_>

Returns a borrowing iterator over the primes.

Example

Basic usage:

const PRIMES: Primes<10> = Primes::new();

let mut primes = PRIMES.iter();

assert_eq!(primes.nth(5), Some(&13));
assert_eq!(primes.next(), Some(&17));
assert_eq!(primes.as_slice(), &[19, 23, 29]);

pub const fn get(&self, index: usize) -> Option<&u32>

Returns a reference to the element at the given index if it is within bounds.

Example

Basic usage:

const PRIMES: Primes<5> = Primes::new();
const THIRD_PRIME: Option<&u32> = PRIMES.get(2);
assert_eq!(THIRD_PRIME, Some(&5));

pub const fn last(&self) -> &u32

Returns a reference to the last prime in self. This is also the largest prime in self.

Example

Basic usage:

const PRIMES: Primes<5> = Primes::new();
assert_eq!(PRIMES.last(), &11);

pub const fn len(&self) -> usize

Returns the number of primes in self.

Example

Basic usage:

const PRIMES: Primes<5> = Primes::new();
assert_eq!(PRIMES.len(), 5);

pub const fn totient(&self, n: u32) -> Result<u32, PartialTotient>

Returns the value of the Euler totient function of n: the number of positive integers up to n that are relatively prime to it.

Example

const CACHE: Primes<3> = Primes::new();
const TOTIENT_OF_6: Result<u32, PartialTotient> = CACHE.totient(2*3);

assert_eq!(TOTIENT_OF_6, Ok(2));

Errors

The totient function is computed here as the product over all factors of the form p^(k-1)*(p-1) where p is the primes in the prime factorization of n and k is their multiplicity. If n contains prime factors that are not part of self, a Result::Err is returned that contains a PartialTotient struct that contains the result from using only the primes in self, as well as the product of the prime factors that are not included in self.

Error example

The number 2450 is equal to 2*5*5*7*7. If the cache does not contain 7 the function runs out of primes after 5, and can not finish the computation:

// Contains the primes [2, 3, 5]
const CACHE: Primes<3> = Primes::new();
const TOTIENT_OF_2450: Result<u32, PartialTotient> = CACHE.totient(2*5*5*7*7);

assert_eq!(
    TOTIENT_OF_2450,
    Err( PartialTotient {
//                 totient(2*5*5) = 20
        totient_using_known_primes: 20,
        product_of_unknown_prime_factors: 49
    })
);

Trait Implementations

impl<const N: usize> Archive for Primes<N>

where [u32; N]: Archive,

type Archived = ArchivedPrimes<N>

The archived representation of this type.

type Resolver = PrimesResolver<N>

The resolver for this type. It must contain all the additional information from serializing needed to make the archived type from the normal type.

fn resolve(&self, resolver: Self::Resolver, out: Place<Self::Archived>)

Creates the archived version of this value at the given position and writes it to the given output.

const COPY_OPTIMIZATION: CopyOptimization<Self> = _

An optimization flag that allows the bytes of this type to be copied directly to a writer instead of calling serialize.

impl<const N: usize> AsRef<[u32]> for Primes<N>

fn as_ref(&self) -> &[u32]

Converts this type into a shared reference of the (usually inferred) input type.

impl<const N: usize> AsRef<[u32; N]> for Primes<N>

fn as_ref(&self) -> &[u32; N]

Converts this type into a shared reference of the (usually inferred) input type.

impl<const N: usize> Clone for Primes<N>

fn clone(&self) -> Primes<N>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<const N: usize> Debug for Primes<N>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const N: usize> Default for Primes<N>

fn default() -> Self

It is a compile error if N is 0.

impl<'de, const N: usize> Deserialize<'de> for Primes<N>

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<__D: Fallible + ?Sized, const N: usize> Deserialize<Primes<N>, __D> for Archived<Primes<N>>

where [u32; N]: Archive, <[u32; N] as Archive>::Archived: Deserialize<[u32; N], __D>,

fn deserialize( &self, deserializer: &mut __D, ) -> Result<Primes<N>, <__D as Fallible>::Error>

Deserializes using the given deserializer

impl<const N: usize> From<Primes<N>> for [u32; N]

fn from(const_primes: Primes<N>) -> Self

Converts to this type from the input type.

impl<const N: usize> Hash for Primes<N>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<const N: usize, I> Index<I> for Primes<N>

where I: SliceIndex<[u32]>,

type Output = <I as SliceIndex<[u32]>>::Output

The returned type after indexing.

fn index(&self, index: I) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<const N: usize> IntoBytes for Primes<N>

where [u32; N]: IntoBytes,

fn as_bytes(&self) -> &[u8]

where Self: Immutable,

Gets the bytes of this value.

fn write_to(&self, dst: &mut [u8]) -> Result<(), SizeError<&Self, &mut [u8]>>

where Self: Immutable,

Writes a copy of self to dst.

fn write_to_prefix( &self, dst: &mut [u8], ) -> Result<(), SizeError<&Self, &mut [u8]>>

where Self: Immutable,

Writes a copy of self to the prefix of dst.

fn write_to_suffix( &self, dst: &mut [u8], ) -> Result<(), SizeError<&Self, &mut [u8]>>

where Self: Immutable,

Writes a copy of self to the suffix of dst.

impl<'a, const N: usize> IntoIterator for &'a Primes<N>

type IntoIter = PrimesIter<'a>

Which kind of iterator are we turning this into?

type Item = &'a u32

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<const N: usize> IntoIterator for Primes<N>

type Item = u32

The type of the elements being iterated over.

type IntoIter = PrimesIntoIter<N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<const N: usize> KnownLayout for Primes<N>

where Self: Sized,

type PointerMetadata = ()

The type of metadata stored in a pointer to Self.

impl<const N: usize> Ord for Primes<N>

fn cmp(&self, other: &Primes<N>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<const N: usize> PartialEq for Primes<N>

fn eq(&self, other: &Primes<N>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<const N: usize> PartialOrd for Primes<N>

fn partial_cmp(&self, other: &Primes<N>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<__S: Fallible + ?Sized, const N: usize> Serialize<__S> for Primes<N>

where [u32; N]: Serialize<__S>,

fn serialize( &self, serializer: &mut __S, ) -> Result<<Self as Archive>::Resolver, <__S as Fallible>::Error>

Writes the dependencies for the object and returns a resolver that can create the archived type.

impl<const N: usize> Serialize for Primes<N>

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<const N: usize> Copy for Primes<N>

impl<const N: usize> Eq for Primes<N>

impl<const N: usize> Immutable for Primes<N>

where [u32; N]: Immutable,

impl<const N: usize> StructuralPartialEq for Primes<N>