Function sieve_lt

pub const fn sieve_lt<const N: usize, const MEM: usize>(
    upper_limit: u64,
) -> Result<[bool; N], SieveError>

Returns an array of size N that indicates which of the N largest integers smaller than upper_limit are prime.

Uses a sieve of size MEM during evaluation, but stores only the requested values in the output array. MEM must be large enough for the sieve to be able to determine the prime status of all numbers in the requested range, that is: MEM^2 must be at least as large as upper_limit.

If you just want the prime status of the first N integers, see sieve, and if you want the prime status of the integers above some number, see sieve_geq.

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

Examples

Basic usage

// The five largest numbers smaller than 30 are 25, 26, 27, 28 and 29.
const N: usize = 5;
const LIMIT: u64 = 30;
// We thus need a memory size of at least 6, since 5*5 < 29, and therefore isn't enough.
const MEM: usize = 6;
const PRIME_STATUSES: [bool; N] = match sieve_lt::<N, MEM>(LIMIT) {Ok(s) => s, Err(_) => panic!()};

assert_eq!(
    PRIME_STATUSES,
//   25     26     27     28     29
    [false, false, false, false, true],
);

Sieve limited ranges of large values. 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_031;
const MEM: usize = isqrt(LIMIT) as usize + 1;
const BIG_PRIME_STATUSES: Result<[bool; N], SieveError> = sieve_lt::<N, MEM>(LIMIT);
assert_eq!(
    BIG_PRIME_STATUSES,
//      5_000_000_028  5_000_000_029  5_000_000_030
    Ok([false,         true,          false]),
);

Errors

Returns an error if upper_limit is larger than MEM^2:

const PS: Result<[bool; 5], SieveError> = sieve_lt::<5, 5>(26);
assert_eq!(PS, Err(SieveError::TooSmallSieveSize));

or smaller than N:

const PS: Result<[bool; 5], SieveError> = sieve_lt::<5, 5>(4);
assert_eq!(PS, Err(SieveError::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<[bool; 5], SieveError> = sieve_lt::<5, 2>(20);

const TOO_LARGE_MEM: Result<[bool; 5], SieveError> = sieve_lt::<5, 1_000_000_000_000>(20);