Crate const_primes
source ·Expand description
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, and currently supports Rust versions 1.67.1 or newer, though enabling feature flags may increase this.
§Example: generate primes at compile time
Generate arrays of prime numbers at compile time with the function primes
which uses a segmented sieve of Eratosthenes:
use const_primes::primes;
const PRIMES: [u32; 10] = primes();
assert_eq!(PRIMES[5], 13);
assert_eq!(PRIMES, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
§Example: use a cache of generated primes for related computations
The struct Primes
is a wrapper around an array of primes 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.count_primes_leq(100);
assert_eq!(PRIMES_LEQ_100, Some(25));
// Prime factorization
assert_eq!(CACHE.prime_factorization(3072).collect::<Vec<_>>(), &[(2, 10), (3, 1)]);
// If questions are asked about numbers outside the cache it returns None
assert!(CACHE.is_prime(1000).is_none());
assert!(CACHE.count_primes_leq(1000).is_none());
§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: sieving
Sieve a range of numbers for their prime status with sieve
:
use const_primes::sieve;
const PRIME_STATUS: [bool; 10] = sieve();
// 0 1 2 3 4 5 6 7 8 9
assert_eq!(PRIME_STATUS, [false, false, true, true, false, true, false, true, false, false]);
§Example: generate the three primes after 5000000031
The crate also provides prime generation and sieving functions that can be used to work with ranges 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!
§Feature flags
std
: implements the Error
trait from the standard library for the error types.
serde
: derives the Serialize
and Deserialize
traits from serde
for the Primes
struct, as well as a few others.
const_assert
: promotes panics that only involve const generics into compile errors. Increases the MSRV of the crate to 1.79.0.
Re-exports§
pub use cache::Primes;
Modules§
- This module contains the implementation of the type
Primes
(and related iterators), which functions as a cache of prime numbers for related computations.
Macros§
- Call
primes_geq
orprimes_lt
, and automatically compute the memory requirement of the sieve.
Enums§
- The error returned by
primes_lt
andprimes_geq
if the input is invalid or does not work to produce the requested primes.
Functions§
- 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. - Returns whether
n
is prime. - Returns the largest integer smaller than or equal to
√n
. - Returns the smallest prime greater than
n
if there is one that can be represented by au64
. - Returns the largest prime smaller than
n
if there is one. - Returns the
N
first prime numbers. - Returns the
N
smallest primes greater than or equal tolower_limit
. - Returns the
N
largest primes less thanupper_limit
. - Returns an array of size
N
where the value at a given index indicates whether the index is prime. - Returns an array of size
N
that indicates which of theN
smallest integers greater than or equal tolower_limit
are prime. - Returns an array of size
N
that indicates which of theN
largest integers smaller thanupper_limit
are prime.