Struct Primes

Source

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

Expand description

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§

Source §

impl<const N: usize> Primes<N>

Source

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();

Source

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);

Source

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);

Source

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));

Source

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));

Source

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));

Source

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));

Source

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));

Source

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]);

Source

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

Returns a reference to the underlying array.

Source

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

Returns a slice that contains the entire underlying array.

Source

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]);

Source

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));

Source

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);

Source

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);

Source

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
    })
);