A Segmented Prime Sieve Algorithm is used to generate all prime numbers within a given range [left, right]. This method combines the Sieve of Eratosthenes to generate primes up to right and a segmented sieve to find primes in the range.

Time complexity: O(n log log n) where n is the value of right

vector<int> primeSieve(int left, int right)
{
    vector<int> primes;
    int sieveArr[right+1] = {0};

    for(long long i=2; i<=right; i++){
        if(sieveArr[i]==0){
            primes.push_back(i);
            for(long long j= i*i; j<=right; j+=i){
                sieveArr[j] = 1;
            }
        }
    }

    vector<int> segment(right-left+1,0);
    vector<int> primeNumbers;

    for(auto p : primes){
        if(p*p > right){break;}
        int start = (left/p) * p;
        if(p>=left and p<=right){
            start = 2 * p;
        }

        for(int j = start; j<=right; j = j + p){
            if(j < left){continue;}
            segment[j - left] = 1;
        }
    }

    for(int i=left; i<=right; i++){
        if(segment[i-left]==0 and i!=1){
            primeNumbers.push_back(i);
        }
    }

    return primeNumbers;
}