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;
}