prime_number_utils/
segmented_sieve.rs

1use crate::{impl_gen_range, BitwiseSieve, GenPrime};
2use std::ops::{Bound::*, RangeBounds};
3
4/// Implementation of the Segmented sieve.
5///
6/// # Examples
7/// ```
8/// # use prime_number_utils::{GenPrime, SegmentedSieve, BitwiseSieve};
9/// # fn main() {
10/// let mut segmented_sieve = SegmentedSieve::new(BitwiseSieve::new());
11/// assert_eq!(segmented_sieve.gen_range(0..10), vec![2, 3, 5, 7]);
12/// # }
13/// ```
14#[derive(Default, Debug, Clone, Eq, PartialEq, Hash)]
15pub struct SegmentedSieve<G: GenPrime = BitwiseSieve> {
16    max: usize,
17    min: usize,
18    gen_prime: G,
19}
20
21impl<G: GenPrime> SegmentedSieve<G> {
22    /// Creates a new sieve.
23    pub fn new(gen_prime: G) -> Self {
24        Self {
25            max: 0,
26            min: 0,
27            gen_prime,
28        }
29    }
30}
31
32impl<G: GenPrime> GenPrime for SegmentedSieve<G> {
33    fn gen(&mut self) -> Vec<usize> {
34        if self.max < 2 {
35            return vec![];
36        }
37        let n = (self.max as f64).sqrt() as usize;
38        let mut primes = self.gen_prime.gen_range(0..n);
39        let mut low = n;
40        let mut high = 2 * n;
41        let mut result = vec![];
42        while low < self.max {
43            if high >= self.max {
44                high = self.max;
45            }
46            let mut sieve = vec![0; n];
47            for i in &primes {
48                let mut lolim = low / i * i;
49                if lolim < low {
50                    lolim += i;
51                }
52                for j in (lolim..high).step_by(*i) {
53                    sieve[j - low] = 1;
54                }
55            }
56            for i in low..high {
57                if sieve[i - low] == 0 {
58                    result.push(i);
59                }
60            }
61            low += n;
62            high += n;
63        }
64        primes.append(&mut result);
65        primes
66    }
67
68    impl_gen_range!();
69}
prime_number_utils/segmented_sieve.rs

prime_number_utils/
segmented_sieve.rs
