← all categories

Segmented Sieve 76122da7

Primes in [l, r] for huge r (beyond what a direct sieve up to r would fit in memory), using base primes up to sqrt(r).

Time: O((r - l + 1) \log\log r + \sqrt r \log\log \sqrt r). tested

content/math/segmented-sieve.h

vector<ll> segmentedSieve(ll l, ll r) {
    l = max(l, 2LL);
    if (l > r) return {};
    auto [isPrimeSmall, basePrimes] = sieve((int)sqrtl((long double)r) + 1);

    vector<bool> isComposite(r - l + 1, false);
    for (ll p : basePrimes) {
        ll start = max(p * p, (l + p - 1) / p * p);
        for (ll j = start; j <= r; j += p) isComposite[j - l] = true;
    }

    vector<ll> primes;
    for (ll i = l; i <= r; i++) if (!isComposite[i - l]) primes.push_back(i);
    return primes;
}