const_primes/
search.rs

1// Copyright 2025 Johanna Sörngård
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! This module contains implementations of functions that search for primes that neighbour a given number.
5
6use crate::is_prime;
7
8/// Generalised function for nearest search by incrementing/decrementing by 1
9/// Any attempt at optimising this would be largely pointless since the largest prime gap under 2^64 is only 1550
10/// And `is_prime`'s trial division already eliminates most of those
11const fn bounded_search(mut n: u64, stride: u64) -> Option<u64> {
12    debug_assert!(stride == 1 || stride == u64::MAX);
13
14    loop {
15        // Addition over Z/2^64, aka regular addition under optimisation flags
16        n = n.wrapping_add(stride);
17
18        // If either condition is met then we started either below or above the smallest or largest prime respectively
19        // Any two values from 2^64-58 to 1 would also work
20        if n == 0u64 || n == u64::MAX {
21            return None;
22        }
23
24        if is_prime(n) {
25            return Some(n);
26        }
27    }
28}
29/// Returns the largest prime smaller than `n` if there is one.
30///
31/// Scans for primes downwards from the input with [`is_prime`].
32///
33/// # Examples
34///
35/// Basic usage:
36///
37/// ```
38/// # use const_primes::previous_prime;
39/// const PREV: Option<u64> = previous_prime(400);
40/// assert_eq!(PREV, Some(397));
41/// ```
42///
43/// There's no prime smaller than two:
44///
45/// ```
46/// # use const_primes::previous_prime;
47/// const NO_SUCH: Option<u64> = previous_prime(2);
48/// assert_eq!(NO_SUCH, None);
49/// ```
50#[must_use = "the function only returns a new value and does not modify its input"]
51pub const fn previous_prime(n: u64) -> Option<u64> {
52    // Adding by 2^64-1 over Z/2^64 is equivalent to subtracting by 1
53    bounded_search(n, u64::MAX)
54}
55
56/// Returns the smallest prime greater than `n` if there is one that
57/// can be represented by a `u64`.
58///
59/// Scans for primes upwards from the input with [`is_prime`].
60///
61/// # Example
62///
63/// Basic usage:
64///
65/// ```
66/// # use const_primes::next_prime;
67/// const NEXT: Option<u64> = next_prime(400);
68/// assert_eq!(NEXT, Some(401));
69/// ```
70///
71/// Primes larger than 18446744073709551557 can not be represented by a `u64`:
72///
73/// ```
74/// # use const_primes::next_prime;
75/// const NO_SUCH: Option<u64> = next_prime(18_446_744_073_709_551_557);
76/// assert_eq!(NO_SUCH, None);
77/// ```
78#[must_use = "the function only returns a new value and does not modify its input"]
79pub const fn next_prime(n: u64) -> Option<u64> {
80    bounded_search(n, 1)
81}
const_primes/search.rs

const_primes/
search.rs
