const_primes/
search.rs

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

const_primes/
search.rs
