Skip to main content

primer/
lib.rs

1//! Cache-aware prime enumeration with a bit-packed segmented sieve.
2//!
3//! Primer generates every prime number up to and including a supplied `u64`
4//! limit. It tracks only odd candidates, stores one candidate per bit, and
5//! reuses a fixed 32 KiB segment while crossing out composites.
6//!
7//! # Memory model
8//!
9//! [`SEGMENT_BYTES`] is the size of Primer's reusable segment buffer. It is not
10//! the total memory used by a call:
11//!
12//! - bootstrap primes up to `sqrt(limit)` require additional memory;
13//! - the returned `Vec<u64>` stores every generated prime;
14//! - normal allocator and process overhead also apply.
15//!
16//! Applications that do not want to retain every prime will eventually benefit
17//! from a streaming API; version 0.3 keeps the original vector-returning
18//! behaviour while establishing a conventional Cargo library interface.
19//!
20//! # Example
21//!
22//! ```
23//! use primer::sieve_primes;
24//!
25//! let primes = sieve_primes(30);
26//! assert_eq!(primes, vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
27//! ```
28
29#![forbid(unsafe_code)]
30
31use std::mem::size_of;
32
33/// Size, in bytes, of Primer's reusable segmented-sieve buffer.
34///
35/// The buffer holds one bit for each odd candidate in the current segment.
36/// Additional memory is used for bootstrap primes and the returned result
37/// vector.
38pub const SEGMENT_BYTES: usize = 32 * 1024;
39
40/// Number of odd candidates represented by one segment.
41pub const SEGMENT_BITS: u64 = (SEGMENT_BYTES * 8) as u64;
42
43const SEGMENT_WORDS: usize = SEGMENT_BYTES / size_of::<u64>();
44
45/// Generate all primes up to and including `limit`.
46///
47/// Primer uses an odd-only, bit-packed segmented Sieve of Eratosthenes. The
48/// reusable segment buffer is [`SEGMENT_BYTES`] bytes. The returned vector uses
49/// additional memory proportional to the number of primes produced.
50///
51/// # Examples
52///
53/// ```
54/// use primer::sieve_primes;
55///
56/// assert_eq!(sieve_primes(1), Vec::<u64>::new());
57/// assert_eq!(sieve_primes(2), vec![2]);
58/// assert_eq!(sieve_primes(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);
59/// ```
60#[must_use]
61pub fn sieve_primes(limit: u64) -> Vec<u64> {
62    if limit < 2 {
63        return Vec::new();
64    }
65
66    if limit < 3 {
67        return vec![2];
68    }
69
70    let square_root = integer_square_root(limit);
71    let highest_half_index = limit / 2;
72
73    let small_primes = small_sieve(square_root);
74    let small_odd_primes: Vec<u64> = small_primes
75        .into_iter()
76        .filter(|&prime| prime > 2)
77        .collect();
78
79    let mut result = Vec::with_capacity(prime_count_capacity(limit));
80    result.push(2);
81
82    let mut segment = vec![0_u64; SEGMENT_WORDS];
83    let mut low_half_index = 0_u64;
84
85    while low_half_index <= highest_half_index {
86        let high_half_index = low_half_index
87            .saturating_add(SEGMENT_BITS - 1)
88            .min(highest_half_index);
89
90        let segment_length = (high_half_index - low_half_index + 1) as usize;
91        let words_needed = (segment_length + 63) / 64;
92
93        segment[..words_needed].fill(u64::MAX);
94
95        if low_half_index == 0 {
96            segment[0] &= !1;
97        }
98
99        for &prime in &small_odd_primes {
100            let first_from_square = (prime * prime - 1) / 2;
101
102            let first_in_segment = if first_from_square >= low_half_index {
103                first_from_square
104            } else {
105                let offset = (low_half_index - first_from_square) % prime;
106                if offset == 0 {
107                    low_half_index
108                } else {
109                    low_half_index + prime - offset
110                }
111            };
112
113            let mut composite_half_index = first_in_segment;
114
115            while composite_half_index <= high_half_index {
116                let local_index = (composite_half_index - low_half_index) as usize;
117                segment[local_index >> 6] &= !(1_u64 << (local_index & 63));
118                composite_half_index += prime;
119            }
120        }
121
122        let trailing_bits = segment_length % 64;
123        if high_half_index == highest_half_index && trailing_bits != 0 {
124            segment[words_needed - 1] &= (1_u64 << trailing_bits) - 1;
125        }
126
127        for (word_index, &word) in segment[..words_needed].iter().enumerate() {
128            let mut remaining = word;
129
130            while remaining != 0 {
131                let trailing_zeros = u64::from(remaining.trailing_zeros());
132                let half_index = low_half_index + ((word_index as u64) << 6) + trailing_zeros;
133                let prime = half_index * 2 + 1;
134
135                if prime <= limit {
136                    result.push(prime);
137                }
138
139                remaining &= remaining - 1;
140            }
141        }
142
143        if high_half_index == highest_half_index {
144            break;
145        }
146
147        low_half_index = high_half_index + 1;
148    }
149
150    result
151}
152
153/// Compatibility name for [`sieve_primes`].
154///
155/// The historical standalone implementation exported `segmented_sieve`.
156/// Keeping this alias makes migration straightforward while `sieve_primes`
157/// serves as the primary crate API.
158#[inline]
159#[must_use]
160pub fn segmented_sieve(limit: u64) -> Vec<u64> {
161    sieve_primes(limit)
162}
163
164fn small_sieve(limit: u64) -> Vec<u64> {
165    if limit < 2 {
166        return Vec::new();
167    }
168
169    let highest_half_index = limit / 2;
170    let word_count = ((highest_half_index >> 6) + 1) as usize;
171    let mut bits = vec![u64::MAX; word_count];
172
173    bits[0] &= !1;
174
175    let square_root = integer_square_root(limit);
176
177    for half_index in 1..=(square_root / 2) {
178        if ((bits[(half_index >> 6) as usize] >> (half_index & 63)) & 1) == 1 {
179            let prime = 2 * half_index + 1;
180            let mut composite_half_index = 2 * half_index * (half_index + 1);
181
182            while composite_half_index <= highest_half_index {
183                bits[(composite_half_index >> 6) as usize] &=
184                    !(1_u64 << (composite_half_index & 63));
185                composite_half_index += prime;
186            }
187        }
188    }
189
190    let mut result = Vec::with_capacity(prime_count_capacity(limit));
191    result.push(2);
192
193    for (word_index, &word) in bits.iter().enumerate() {
194        let lowest_value = ((word_index as u64) << 7) + 1;
195        if lowest_value > limit {
196            break;
197        }
198
199        let mut remaining = word;
200
201        while remaining != 0 {
202            let trailing_zeros = u64::from(remaining.trailing_zeros());
203            let half_index = ((word_index as u64) << 6) + trailing_zeros;
204            let prime = half_index * 2 + 1;
205
206            if prime <= limit {
207                result.push(prime);
208            }
209
210            remaining &= remaining - 1;
211        }
212    }
213
214    result
215}
216
217#[inline]
218fn integer_square_root(value: u64) -> u64 {
219    if value < 2 {
220        return value;
221    }
222
223    let mut estimate = (value as f64).sqrt() as u64;
224
225    while estimate > value / estimate {
226        estimate -= 1;
227    }
228
229    loop {
230        let next = estimate + 1;
231
232        if next > value / next {
233            break;
234        }
235
236        estimate = next;
237    }
238
239    estimate
240}
241
242#[inline]
243fn prime_count_capacity(limit: u64) -> usize {
244    if limit < 10 {
245        return 4;
246    }
247
248    let floating_limit = limit as f64;
249    let estimate = floating_limit / floating_limit.ln() * 1.15 + 1.0;
250    let maximum_capacity = (isize::MAX as usize) / size_of::<u64>();
251
252    if !estimate.is_finite() || estimate >= maximum_capacity as f64 {
253        maximum_capacity
254    } else {
255        estimate as usize
256    }
257}
258
259#[cfg(test)]
260mod tests {
261    use super::*;
262
263    fn reference_sieve(limit: u64) -> Vec<u64> {
264        if limit < 2 {
265            return Vec::new();
266        }
267
268        let length = usize::try_from(limit + 1).expect("test limit must fit usize");
269        let mut prime = vec![true; length];
270        prime[0] = false;
271        prime[1] = false;
272
273        let square_root = integer_square_root(limit) as usize;
274        for candidate in 2..=square_root {
275            if prime[candidate] {
276                let mut multiple = candidate * candidate;
277                while multiple < length {
278                    prime[multiple] = false;
279                    multiple += candidate;
280                }
281            }
282        }
283
284        prime
285            .iter()
286            .enumerate()
287            .filter_map(|(value, &is_prime)| is_prime.then_some(value as u64))
288            .collect()
289    }
290
291    #[test]
292    fn handles_edge_cases() {
293        assert!(sieve_primes(0).is_empty());
294        assert!(sieve_primes(1).is_empty());
295        assert_eq!(sieve_primes(2), vec![2]);
296        assert_eq!(sieve_primes(3), vec![2, 3]);
297    }
298
299    #[test]
300    fn produces_known_small_sets() {
301        assert_eq!(sieve_primes(10), vec![2, 3, 5, 7]);
302        assert_eq!(sieve_primes(30), vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29]);
303    }
304
305    #[test]
306    fn produces_known_prime_counts() {
307        for (limit, expected_count) in [
308            (100, 25),
309            (1_000, 168),
310            (10_000, 1_229),
311            (100_000, 9_592),
312            (500_000, 41_538),
313            (1_000_000, 78_498),
314        ] {
315            assert_eq!(
316                sieve_primes(limit).len(),
317                expected_count,
318                "wrong prime count for limit {limit}"
319            );
320        }
321    }
322
323    #[test]
324    fn matches_reference_across_small_limits() {
325        for limit in 0..=512 {
326            assert_eq!(
327                sieve_primes(limit),
328                reference_sieve(limit),
329                "mismatch for limit {limit}"
330            );
331        }
332    }
333
334    #[test]
335    fn matches_reference_at_representative_limits() {
336        for limit in [1_000, 10_000, 100_000, 500_000, 1_100_000] {
337            assert_eq!(
338                sieve_primes(limit),
339                reference_sieve(limit),
340                "mismatch for limit {limit}"
341            );
342        }
343    }
344
345    #[test]
346    fn preserves_known_boundaries() {
347        let primes = sieve_primes(500_000);
348        assert_eq!(primes[9], 29);
349        assert_eq!(primes[9_999], 104_729);
350        assert_eq!(primes[10_000], 104_743);
351        assert_eq!(primes.last(), Some(&499_979));
352
353        assert_eq!(sieve_primes(29).last(), Some(&29));
354    }
355
356    #[test]
357    fn compatibility_alias_matches_primary_api() {
358        for limit in [0, 2, 3, 10, 1_000, 500_000] {
359            assert_eq!(segmented_sieve(limit), sieve_primes(limit));
360        }
361    }
362
363    #[test]
364    fn integer_square_root_is_safe_at_boundaries() {
365        assert_eq!(integer_square_root(0), 0);
366        assert_eq!(integer_square_root(1), 1);
367        assert_eq!(integer_square_root(4), 2);
368        assert_eq!(integer_square_root(15), 3);
369        assert_eq!(integer_square_root(16), 4);
370        assert_eq!(integer_square_root(17), 4);
371        assert_eq!(integer_square_root(1_u64 << 52), 1_u64 << 26);
372        assert_eq!(integer_square_root(u64::MAX), 4_294_967_295);
373    }
374
375    #[test]
376    fn segment_geometry_is_consistent() {
377        assert_eq!(SEGMENT_BYTES, 32 * 1024);
378        assert_eq!(SEGMENT_BITS, 262_144);
379        assert_eq!(SEGMENT_WORDS * size_of::<u64>(), SEGMENT_BYTES);
380    }
381}