#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Function to perform the simple sieve of Eratosthenes up to sqrt(b)
vector<int> simple_sieve(int limit) {
    vector<bool> is_prime(limit + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

// Function to find all primes in the range [a, b] using the segmented sieve
void segmented_sieve(int a, int b) {
    int limit = sqrt(b);
    vector<int> primes = simple_sieve(limit);

    // Create a boolean array for the range [a, b]
    vector<bool> is_prime_segment(b - a + 1, true);

    // Mark multiples of each prime in the range [a, b]
    for (int prime : primes) {
        int start = max(prime * prime, a + (prime - a % prime) % prime);

        for (int j = start; j <= b; j += prime) {
            is_prime_segment[j - a] = false;
        }
    }

    // If a is 1, then it's not a prime number
    if (a == 1) {
        is_prime_segment[0] = false;
    }

    // Output all primes in the range [a, b]
    cout << "Prime numbers in the range [" << a << ", " << b << "] are:" << endl;
    for (int i = 0; i <= b - a; i++) {
        if (is_prime_segment[i]) {
            cout << (a + i) << " ";
        }
    }
    cout << endl;
}

int main() {
    int a = 10, b = 50;
    segmented_sieve(a, b);
    return 0;
}