1#![forbid(unsafe_code)]
30
31use std::mem::size_of;
32
33pub const SEGMENT_BYTES: usize = 32 * 1024;
39
40pub const SEGMENT_BITS: u64 = (SEGMENT_BYTES * 8) as u64;
42
43const SEGMENT_WORDS: usize = SEGMENT_BYTES / size_of::<u64>();
44
45#[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#[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}