prime_number_utils/
bitwise_sieve.rs

1use crate::{impl_gen_range, GenPrime};
2use std::ops::{Bound::*, RangeBounds};
3
4#[derive(Default, Debug, Clone, Copy, Eq, PartialEq, Hash)]
5/// Generates prime numbers using bitwise.
6///
7/// # Examples
8/// ```
9/// # use prime_number_utils::{GenPrime, BitwiseSieve};
10/// # fn main() {
11/// let mut bitwise_sieve = BitwiseSieve::new();
12/// assert_eq!(bitwise_sieve.gen_range(0..10), vec![2, 3, 5, 7]);
13/// # }
14/// ```
15pub struct BitwiseSieve {
16    max: usize,
17    min: usize,
18}
19
20impl BitwiseSieve {
21    /// Creates a new sieve.
22    pub fn new() -> Self {
23        Self::default()
24    }
25}
26
27impl GenPrime for BitwiseSieve {
28    fn gen(&mut self) -> Vec<usize> {
29        let not_prime = |sieve: &Vec<usize>, n: usize| sieve[n / 64] & (1 << ((n >> 1) & 31));
30        if self.max < 2 {
31            return vec![];
32        }
33        let mut sieve = vec![0; self.max / 64 + 1];
34        for i in (3..=(self.max as f64).sqrt() as usize).step_by(2) {
35            if not_prime(&sieve, i) == 0 {
36                let k = i << 1;
37                for j in (i.pow(2)..self.max).step_by(k) {
38                    sieve[j / 64] |= 1 << ((j >> 1) & 31);
39                }
40            }
41        }
42        let mut primes = vec![2];
43        for i in (3..=self.max).step_by(2) {
44            if not_prime(&sieve, i) == 0 {
45                primes.push(i);
46            }
47        }
48        primes
49    }
50
51    impl_gen_range!();
52}
prime_number_utils/bitwise_sieve.rs

prime_number_utils/
bitwise_sieve.rs
