Crate const_primes

Generate and work with prime numbers in const contexts.

This crate lets you for example pre-compute prime numbers at compile time, store them in the binary, and use them later for related computations, or check whether a number is prime in a const function.

no_std compatible when the serde feature is disabled.

This version of the crate supports Rust versions 1.81.0 and up, while versions 0.8.7 and older support Rust versions 1.67.1 and up.

Example: generate primes at compile time and reuse it for related computations

The struct Primes is a wrapper around an array of primes generated by a segmented sieve of Eratosthenes and can be used as a cache of prime numbers for related computations:

// The first 100 primes
const CACHE: Primes<100> = Primes::new();

// Primality testing
const CHECK_42: Option<bool> = CACHE.is_prime(42);
const CHECK_541: Option<bool> = CACHE.is_prime(541);
assert_eq!(CHECK_42, Some(false));
assert_eq!(CHECK_541, Some(true));

// Prime counting
const PRIMES_LEQ_100: Option<usize> = CACHE.prime_pi(100);
assert_eq!(PRIMES_LEQ_100, Some(25));

// Prime factorization
assert_eq!(CACHE.prime_factorization(3072).collect::<Vec<_>>(), &[(2, 10), (3, 1)]);
// and more!

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

Want only the numbers? Use the function primes, or convert the cache into an array:

use const_primes::{primes, Primes};

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

const PRIMES_ARRAY1: [u32; 10] = primes();
const PRIMES_ARRAY2: [u32; 10] = CACHE.into_array();

assert_eq!(PRIMES_ARRAY1, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
assert_eq!(PRIMES_ARRAY1, PRIMES_ARRAY2);

Example: primality checking

Use is_prime to test whether a given number is prime:

use const_primes::is_prime;

const CHECK: bool = is_prime(18_446_744_073_709_551_557);

assert!(CHECK);

Example: generate the three primes after 5000000031

The crate also provides prime generation and sieving functions that can be used to work with ranges of large numbers that don’t start at zero, e.g. primes_geq and sieve_lt. These functions can use large sieves to compute large primes, but don’t need to return the entire sieve, just the requested numbers. They are most conveniently used through the macros primes_segment! and sieve_segment! that automatically compute the size of the sieve that’s needed for a certain computation.

Compute 3 primes greater than or equal to 5000000031:

use const_primes::{primes_segment, GenerationError};

const N: usize = 3;
const PRIMES_GEQ: Result<[u64; N], GenerationError> = primes_segment!(N; >= 5_000_000_031);

assert_eq!(PRIMES_GEQ, Ok([5_000_000_039, 5_000_000_059, 5_000_000_063]));

Example: find the next or previous prime numbers

Find the next or previous prime numbers with next_prime and previous_prime if they exist:

use const_primes::{previous_prime, next_prime};

const NEXT: Option<u64> = next_prime(25);
const PREV: Option<u64> = previous_prime(25);
const NO_SUCH: Option<u64> = previous_prime(2);
const TOO_BIG: Option<u64> = next_prime(u64::MAX);

assert_eq!(NEXT, Some(29));
assert_eq!(PREV, Some(23));
assert_eq!(NO_SUCH, None);
assert_eq!(TOO_BIG, None);

and more!

Features

serde: derives the Serialize and Deserialize traits from the serde crte for the Primes struct, as well as a few others. Uses the serde_arrays crate to do this, and that crate uses the standard library.

zerocopy: derives the IntoBytes trait from the zerocopy crate for the Primes struct.

rkyv: derives the Serialize, Deserialize, and Archive traits from the rkyv crate for the Primes struct.

Re-exports

• pub use cache::Primes;

Modules

• cache
  This module contains the implementation of the type Primes (and related iterators), which functions as a cache of prime numbers for related computations.

Macros

• primes_segment
  Call primes_geq or primes_lt, and automatically compute the memory requirement of the sieve.
• sieve_segment
  Call sieve_geq or sieve_lt, and automatically compute the memory requirement of the sieve.

Enums

• GenerationError
  The error returned by primes_lt and primes_geq if the input is invalid or does not work to produce the requested primes.
• SieveError
  The error returned by sieve_lt and sieve_geq if the input is invalid or does not work to sieve the requested range.

Functions

• is_prime
  Returns whether n is prime.
• isqrt
  Returns the largest integer smaller than or equal to √n.
• next_prime
  Returns the smallest prime greater than n if there is one that can be represented by a u64.
• previous_prime
  Returns the largest prime smaller than n if there is one.
• prime_pi
  Returns an array of size N where the value at a given index is how many primes are less than or equal to the index.
• primes
  Returns the N first prime numbers.
• primes_geq
  Returns the N smallest primes greater than or equal to lower_limit.
• primes_lt
  Returns the N largest primes less than upper_limit.
• sieve
  Returns an array of size N where the value at a given index indicates whether the index is prime.
• sieve_geq
  Returns an array of size N that indicates which of the N smallest integers greater than or equal to lower_limit are prime.
• sieve_lt
  Returns an array of size N that indicates which of the N largest integers smaller than upper_limit are prime.