Segmented sieve of Eratosthenes implementation in C++

segmented_sieve.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<ll> sieve(ll n) {
    vector<ll> is_prime(n + 1, true), res;
    for (ll i = 2; i <= n; i++) {
        if (is_prime[i]) {
            res.push_back(i);
            for (ll j = i * i; j <= n; j += i) is_prime[j] = false;
        }
    }
    return res;
}

vector<bool> segmented_sieve(ll l, ll r) {
    vector<ll> primes = sieve(sqrt(r));
    vector<bool> is_prime(r - l + 1, true);
    for(ll i : primes){
        ll min_mul;
        if(i > l) min_mul = i;
        else {
            min_mul = l;
            if(l % i) min_mul += i - l % i;
        }
        for(ll j = min_mul; j - l < is_prime.size(); j += i){
            if(j == i) continue;
            is_prime[j - l] = false;
        }
    }
    if (l == 1) is_prime[0] = false;
    return is_prime;
}

int main() {
    ll l, r;
    cin >> l >> r;
    vector<bool> is_prime_segmented = segmented_sieve(l, r);
    for(ll i = l; i <= r; i++){
        if(is_prime_segmented[i - l]) cout << i << '\n';
    }
}