fn sieve_dense(bits: &mut [u64], l: u32, r: u32, wheel: &Wheel)Examples found in repository?
crates/competitive/src/math/prime_list.rs (line 372)
356 pub fn reserve(&mut self, max_n: u32) {
357 if max_n <= self.max_n || max_n < 2 {
358 return;
359 }
360 let limit = max_n.saturating_add(1);
361 self.bit_len = to_ordinal(limit) as usize;
362 if limit <= SQRT_THRESHOLD {
363 self.bits = SQRT_BITS[..self.bit_len.div_ceil(64)].to_vec();
364 } else {
365 self.bits = vec![!0; self.bit_len.div_ceil(64)];
366 let (wheels, medium_primes_begin) = make_wheels();
367 const DENSE_BLOCK: u32 = 1 << 25;
368 for start in (0..limit).step_by(DENSE_BLOCK as usize) {
369 let right = start.saturating_add(DENSE_BLOCK).min(limit);
370 for wheel in &wheels {
371 let left = start / wheel.product * wheel.product;
372 sieve_dense(&mut self.bits, to_ordinal(left), to_ordinal(right), wheel);
373 }
374 }
375
376 let steps = ordinal_steps();
377 let mut positions: Vec<_> = SQRT_PRIMES.iter().map(|&p| to_ordinal(p * p)).collect();
378 let mut states: Vec<_> = SQRT_PRIMES
379 .iter()
380 .map(|&p| STATES[(p % PERIOD) as usize])
381 .collect();
382 const SPARSE_BLOCK: u32 = 1 << 22;
383 for start in (0..limit).step_by(SPARSE_BLOCK as usize) {
384 let right = to_ordinal(start.saturating_add(SPARSE_BLOCK).min(limit));
385 for i in medium_primes_begin..SQRT_PRIME_COUNT {
386 (positions[i], states[i]) =
387 sieve_sparse(&mut self.bits, positions[i], right, i, states[i], &steps);
388 }
389 }
390 for (value, &sqrt_bits) in self.bits.iter_mut().zip(&SQRT_BITS) {
391 *value = sqrt_bits;
392 }
393 }
394
395 self.prime_count = WHEEL_PRIMES.partition_point(|&p| p <= max_n);
396 if let Some((&last, rest)) = self.bits.split_last() {
397 self.prime_count += rest
398 .iter()
399 .map(|word| word.count_ones() as usize)
400 .sum::<usize>();
401 let last_mask = if self.bit_len.is_multiple_of(64) {
402 !0
403 } else {
404 (1 << (self.bit_len % 64)) - 1
405 };
406 self.prime_count += (last & last_mask).count_ones() as usize;
407 }
408 self.max_n = max_n;
409 }