cp_library_rs/data_structure/
segmented_sieve.rs

1//! 区間篩
2
3/// 区間 $`[l,r)`$ の素数を列挙する
4/// - 時間計算量: $`O((\sqrt{r} + (r - l)) \log \log r)`$
5pub fn segmented_sieve(l: usize, r: usize) -> Vec<usize> {
6    let l = l.max(2);
7    let r = r.max(l);
8    let MAX = (r as f64).sqrt() as usize + 10;
9    let mut divisors = vec![true; MAX];
10    (divisors[0], divisors[1]) = (false, false);
11    let mut sieve = vec![true; r - l];
12
13    for p in 2..MAX {
14        if !divisors[p] {
15            continue;
16        }
17        let mut i = 2;
18        while p * i < MAX {
19            divisors[p * i] = false;
20            i += 1;
21        }
22        let mut k = l.div_ceil(p) * p;
23        while k < r {
24            if k > p && l <= k && k < r {
25                sieve[k - l] = false;
26            }
27            k += p;
28        }
29    }
30
31    sieve
32        .iter()
33        .zip(l..)
34        .filter_map(|(&is_prime, x)| is_prime.then_some(x))
35        .collect()
36}