Function sieve_geq

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

Returns an array of size N that indicates which of the N smallest integers greater than or equal to lower_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 larger than lower_limit + N.

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

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

Examples

The size of the sieve, MEM, must be large enough for the largest sieved number to be smaller than MEM^2:

// The three numbers larger than or equal to 9 are 9, 10 and 11.
const N: usize = 3;
const LIMIT: u64 = 9;
// We thus need a memory size of at least 4, since 3*3 < 11, and therefore isn't enough.
const MEM: usize = 4;
const PRIME_STATUS: [bool; N] = match sieve_geq::<N, MEM>(LIMIT) {Ok(s) => s, Err(_) => panic!()};
//                        9,     10,    11
assert_eq!(PRIME_STATUS, [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_038;
const MEM: usize = isqrt(LIMIT) as usize + 1 + N;
const BIG_PRIME_STATUS: Result<[bool; N], SieveError> = sieve_geq::<N, MEM>(LIMIT);
//                               5_000_000_038  5_000_000_039  5_000_000_040
assert_eq!(BIG_PRIME_STATUS, Ok([false,         true,          false]));

Errors

Returns an error if MEM + lower_limit is larger than MEM^2 or doesn’t fit in a u64:

const P1: Result<[bool; 5], SieveError> = sieve_geq::<5, 5>(21);
const P2: Result<[bool; 5], SieveError> = sieve_geq::<5, 5>(u64::MAX);
assert_eq!(P1, Err(SieveError::TooSmallSieveSize));
assert_eq!(P2, Err(SieveError::TotalDoesntFitU64));

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_geq::<5, 2>(100);

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