1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

//! 区間篩

/// 区間 $`[l,r)`$ の素数を列挙する
/// - 時間計算量: $`O((\sqrt{r} + (r - l)) \log \log r)`$
pub fn segmented_sieve(l: usize, r: usize) -> Vec<usize> {
    let l = l.max(2);
    let r = r.max(l);
    let MAX = (r as f64).sqrt() as usize + 10;
    let mut divisors = vec![true; MAX];
    (divisors[0], divisors[1]) = (false, false);
    let mut sieve = vec![true; r - l];

    for p in 2..MAX {
        if !divisors[p] {
            continue;
        }
        let mut i = 2;
        while p * i < MAX {
            divisors[p * i] = false;
            i += 1;
        }
        let mut k = (l + p - 1) / p * p;
        while k < r {
            if k > p && l <= k && k < r {
                sieve[k - l] = false;
            }
            k += p;
        }
    }

    sieve
        .iter()
        .zip(l..)
        .filter_map(|(&is_prime, x)| is_prime.then_some(x))
        .collect()
}