Function primes_lt

pub const fn primes_lt<const N: usize, const MEM: usize>(
    upper_limit: u64,
) -> Result<[u64; N], GenerationError>

Returns the N largest primes less than upper_limit.

This function uses a segmented sieve of size MEM for computation, but only stores the N requested primes in the output array.

Set MEM such that MEM*MEM >= upper_limit.

If you want to compute primes that are larger than some limit, take a look at primes_geq.

If you do not wish to compute the size requirement of the sieve manually, take a look at primes_segment!.

Example

Basic usage:

// Sieving up to 100 means the sieve needs to be of size ceil(sqrt(100)) = 10.
// However, we only save the 4 largest primes in the constant.
const PRIMES: [u64;4] = match primes_lt::<4, 10>(100) {Ok(ps) => ps, Err(_) => panic!()};
assert_eq!(PRIMES, [79, 83, 89, 97]);

Compute limited ranges of large primes. Functions provided by the crate can help you compute the needed sieve size:

use const_primes::isqrt;
const N: usize = 3;
const LIMIT: u64 = 5_000_000_030;
const MEM: usize = isqrt(LIMIT) as usize + 1;
const BIG_PRIMES: Result<[u64; N], GenerationError> = primes_lt::<N, MEM>(LIMIT);

assert_eq!(BIG_PRIMES, Ok([4_999_999_903, 4_999_999_937, 5_000_000_029]));

Errors

If the number of primes requested, N, is larger than the number of primes that exists below the upper_limit this function returns an error:

const N: usize = 9;
const PRIMES: Result<[u64; N], GenerationError> = primes_lt::<N, N>(10);
assert_eq!(PRIMES, Err(GenerationError::OutOfPrimes));

It also returns an error if upper_limit is larger than MEM^2 or if upper_limit is smaller than or equal to 2:

const TOO_LARGE_LIMIT: Result<[u64; 3], GenerationError> = primes_lt::<3, 5>(26);
const TOO_SMALL_LIMIT: Result<[u64; 1], GenerationError> = primes_lt::<1, 1>(1);
assert_eq!(TOO_LARGE_LIMIT, Err(GenerationError::TooSmallSieveSize));
assert_eq!(TOO_SMALL_LIMIT, Err(GenerationError::TooSmallLimit));

It is a compile error if MEM is smaller than N, or if MEM^2 does not fit in a u64:

const TOO_SMALL_MEM: Result<[u64; 5], GenerationError> = primes_lt::<5, 2>(20);

const TOO_BIG_MEM: Result<[u64; 10], GenerationError> = primes_lt::<10, 1_000_000_000_000>(100);