nekolib/math/
compact_sieve.rs

1//! 篩。
2
3/// 篩。
4pub struct CompactSieve {
5    n: usize,
6    is_prime: Vec<u64>,
7}
8
9const WORD_SIZE: usize = 64;
10
11impl CompactSieve {
12    pub fn new(n: usize) -> Self {
13        let mut is_prime = vec![0xAAAAAAAAAAAAAAAA; 1 + n / WORD_SIZE];
14        is_prime[0] |= 1 << 2;
15        for i in (3..=n).take_while(|&i| i * i <= n) {
16            if is_prime[i / WORD_SIZE] >> (i % WORD_SIZE) & 1 == 0 {
17                continue;
18            }
19            for j in i..=n / i {
20                let ij = i * j;
21                is_prime[ij / WORD_SIZE] &= !(1_u64 << (ij % WORD_SIZE));
22            }
23        }
24        Self { n, is_prime }
25    }
26    pub fn is_prime(&self, i: usize) -> bool {
27        self.is_prime[i / WORD_SIZE] >> (i % WORD_SIZE) & 1 == 1
28    }
29    pub fn primes(&self) -> impl Iterator<Item = usize> + '_ {
30        (2..=self.n).filter(move |&i| self.is_prime(i))
31    }
32}
nekolib/math/compact_sieve.rs

nekolib/math/
compact_sieve.rs
