use_prime/
lib.rs

1#![forbid(unsafe_code)]
2#![doc = include_str!("../README.md")]
3
4//! Small prime number utilities for `RustUse`.
5
6/// Primality checks and neighboring prime search.
7pub mod primality {
8    /// Returns `true` when `n` is prime.
9    ///
10    /// `0` and `1` are not prime. `2` and `3` are prime. Even values greater
11    /// than `2` are not prime.
12    #[must_use]
13    pub fn is_prime(n: u64) -> bool {
14        match n {
15            0 | 1 => false,
16            2 | 3 => true,
17            _ if n % 2 == 0 => false,
18            _ => {
19                let mut divisor = 3_u64;
20
21                while divisor <= n / divisor {
22                    if n % divisor == 0 {
23                        return false;
24                    }
25
26                    divisor += 2;
27                }
28
29                true
30            },
31        }
32    }
33
34    /// Returns `true` when `n` is composite.
35    ///
36    /// Composite values are integers greater than `1` that are not prime.
37    #[must_use]
38    pub fn is_composite(n: u64) -> bool {
39        n > 1 && !is_prime(n)
40    }
41
42    /// Returns the smallest prime strictly greater than `n`.
43    ///
44    /// Returns `None` when no larger `u64` value exists.
45    #[must_use]
46    pub fn next_prime(n: u64) -> Option<u64> {
47        if n < 2 {
48            return Some(2);
49        }
50
51        let mut candidate = n.checked_add(1)?;
52
53        if candidate == 2 {
54            return Some(2);
55        }
56
57        if candidate % 2 == 0 {
58            candidate = candidate.checked_add(1)?;
59        }
60
61        loop {
62            if is_prime(candidate) {
63                return Some(candidate);
64            }
65
66            candidate = candidate.checked_add(2)?;
67        }
68    }
69
70    /// Returns the largest prime strictly less than `n`.
71    ///
72    /// Returns `None` for `0`, `1`, and `2`.
73    #[must_use]
74    pub fn previous_prime(n: u64) -> Option<u64> {
75        if n <= 2 {
76            return None;
77        }
78
79        if n == 3 {
80            return Some(2);
81        }
82
83        let mut candidate = n - 1;
84
85        if candidate % 2 == 0 {
86            candidate -= 1;
87        }
88
89        loop {
90            if is_prime(candidate) {
91                return Some(candidate);
92            }
93
94            if candidate <= 3 {
95                return Some(2);
96            }
97
98            candidate -= 2;
99        }
100    }
101}
102
103/// Prime factorization helpers.
104pub mod factorization {
105    /// Returns the prime factorization of `n` as `(prime, exponent)` pairs.
106    ///
107    /// `0` and `1` return an empty vector in this crate. Results are sorted in
108    /// ascending prime order.
109    #[must_use]
110    pub fn factorization(n: u64) -> Vec<(u64, u32)> {
111        if n < 2 {
112            return Vec::new();
113        }
114
115        let mut remaining = n;
116        let mut factors = Vec::new();
117        let mut exponent = 0_u32;
118
119        while remaining % 2 == 0 {
120            remaining /= 2;
121            exponent += 1;
122        }
123
124        if exponent > 0 {
125            factors.push((2, exponent));
126        }
127
128        let mut divisor = 3_u64;
129        while divisor <= remaining / divisor {
130            let mut local_exponent = 0_u32;
131
132            while remaining % divisor == 0 {
133                remaining /= divisor;
134                local_exponent += 1;
135            }
136
137            if local_exponent > 0 {
138                factors.push((divisor, local_exponent));
139            }
140
141            divisor += 2;
142        }
143
144        if remaining > 1 {
145            factors.push((remaining, 1));
146        }
147
148        factors
149    }
150
151    /// Returns the prime factors of `n`, including repeated multiplicities.
152    ///
153    /// `0` and `1` return an empty vector in this crate.
154    #[must_use]
155    pub fn prime_factors(n: u64) -> Vec<u64> {
156        factorization(n)
157            .into_iter()
158            .flat_map(|(prime, exponent)| core::iter::repeat_n(prime, exponent as usize))
159            .collect()
160    }
161
162    /// Returns the unique prime factors of `n` in ascending order.
163    ///
164    /// `0` and `1` return an empty vector in this crate.
165    #[must_use]
166    pub fn unique_prime_factors(n: u64) -> Vec<u64> {
167        factorization(n)
168            .into_iter()
169            .map(|(prime, _)| prime)
170            .collect()
171    }
172}
173
174/// Prime sieves and sieve-backed prime generation.
175pub mod sieve {
176    /// Returns a boolean sieve up to and including `limit`.
177    ///
178    /// The returned vector has length `limit + 1`, and index `i` is `true`
179    /// exactly when `i` is prime.
180    #[must_use]
181    pub fn sieve(limit: usize) -> Vec<bool> {
182        let mut flags = vec![true; limit.saturating_add(1)];
183
184        if let Some(first) = flags.get_mut(0) {
185            *first = false;
186        }
187
188        if let Some(second) = flags.get_mut(1) {
189            *second = false;
190        }
191
192        let mut candidate = 2_usize;
193        while candidate <= limit / candidate {
194            if flags[candidate] {
195                let mut multiple = candidate * candidate;
196                while multiple <= limit {
197                    flags[multiple] = false;
198                    multiple += candidate;
199                }
200            }
201
202            candidate += 1;
203        }
204
205        flags
206    }
207
208    /// Returns every prime less than or equal to `limit`.
209    #[must_use]
210    pub fn primes_up_to(limit: usize) -> Vec<usize> {
211        sieve(limit)
212            .into_iter()
213            .enumerate()
214            .filter_map(|(value, is_prime)| is_prime.then_some(value))
215            .collect()
216    }
217}
218
219pub use factorization::{factorization, prime_factors, unique_prime_factors};
220pub use primality::{is_composite, is_prime, next_prime, previous_prime};
221pub use sieve::{primes_up_to, sieve};
222
223#[cfg(test)]
224mod tests {
225    use super::{
226        factorization, is_composite, is_prime, next_prime, previous_prime, prime_factors,
227        primes_up_to, sieve, unique_prime_factors,
228    };
229
230    #[test]
231    fn classifies_zero_one_two_and_three() {
232        assert!(!is_prime(0));
233        assert!(!is_prime(1));
234        assert!(is_prime(2));
235        assert!(is_prime(3));
236    }
237
238    #[test]
239    fn rejects_small_composites() {
240        assert!(!is_prime(4));
241        assert!(is_prime(5));
242        assert!(!is_prime(9));
243        assert!(is_prime(11));
244    }
245
246    #[test]
247    fn rejects_even_composites_greater_than_two() {
248        assert!(!is_prime(6));
249        assert!(!is_prime(42));
250        assert!(!is_prime(10_000));
251    }
252
253    #[test]
254    fn rejects_square_composites() {
255        assert!(!is_prime(49));
256        assert!(!is_prime(121));
257    }
258
259    #[test]
260    fn accepts_larger_primes() {
261        assert!(is_prime(7_919));
262        assert!(is_prime(10_007));
263    }
264
265    #[test]
266    fn rejects_larger_composites() {
267        assert!(!is_prime(7_920));
268        assert!(!is_prime(10_001));
269    }
270
271    #[test]
272    fn classifies_composite_values() {
273        assert!(!is_composite(0));
274        assert!(!is_composite(1));
275        assert!(!is_composite(2));
276        assert!(is_composite(4));
277        assert!(is_composite(9));
278    }
279
280    #[test]
281    fn finds_next_prime() {
282        assert_eq!(next_prime(0), Some(2));
283        assert_eq!(next_prime(1), Some(2));
284        assert_eq!(next_prime(2), Some(3));
285        assert_eq!(next_prime(14), Some(17));
286    }
287
288    #[test]
289    fn finds_previous_prime() {
290        assert_eq!(previous_prime(0), None);
291        assert_eq!(previous_prime(1), None);
292        assert_eq!(previous_prime(2), None);
293        assert_eq!(previous_prime(3), Some(2));
294        assert_eq!(previous_prime(13), Some(11));
295    }
296
297    #[test]
298    fn computes_prime_factors() {
299        assert_eq!(prime_factors(0), Vec::<u64>::new());
300        assert_eq!(prime_factors(1), Vec::<u64>::new());
301        assert_eq!(prime_factors(2), vec![2]);
302        assert_eq!(prime_factors(12), vec![2, 2, 3]);
303        assert_eq!(prime_factors(60), vec![2, 2, 3, 5]);
304    }
305
306    #[test]
307    fn computes_unique_prime_factors() {
308        assert_eq!(unique_prime_factors(0), Vec::<u64>::new());
309        assert_eq!(unique_prime_factors(1), Vec::<u64>::new());
310        assert_eq!(unique_prime_factors(2), vec![2]);
311        assert_eq!(unique_prime_factors(12), vec![2, 3]);
312    }
313
314    #[test]
315    fn computes_factorization_pairs() {
316        assert_eq!(factorization(0), Vec::<(u64, u32)>::new());
317        assert_eq!(factorization(1), Vec::<(u64, u32)>::new());
318        assert_eq!(factorization(2), vec![(2, 1)]);
319        assert_eq!(factorization(12), vec![(2, 2), (3, 1)]);
320        assert_eq!(factorization(60), vec![(2, 2), (3, 1), (5, 1)]);
321    }
322
323    #[test]
324    fn builds_sieve_flags() {
325        assert_eq!(sieve(0), vec![false]);
326        assert_eq!(sieve(1), vec![false, false]);
327        assert_eq!(sieve(2), vec![false, false, true]);
328
329        let flags = sieve(10);
330        assert_eq!(
331            flags,
332            vec![
333                false, false, true, true, false, true, false, true, false, false, false
334            ]
335        );
336    }
337
338    #[test]
339    fn lists_primes_up_to_limit() {
340        assert_eq!(primes_up_to(0), Vec::<usize>::new());
341        assert_eq!(primes_up_to(1), Vec::<usize>::new());
342        assert_eq!(primes_up_to(2), vec![2]);
343        assert_eq!(primes_up_to(10), vec![2, 3, 5, 7]);
344        assert_eq!(primes_up_to(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);
345    }
346}
use_prime/lib.rs

use_prime/
lib.rs
