Prime Numbers in Range (Segmented Sieve of Eratosthenes)

Prime Numbers in Range (Segmented Sieve of Eratosthenes)

Segmented Sieve is used for finding prime numbers in the given range (low and high) with less auxiliary space . The problem with simple Sieve of Eratosthenes is that it takes more memory for given long ranges (low and high).

PROBLEM STATEMENT :

Given a range [low, high], print all primes in this range?

Input : The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output : For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

 

For example,

Input : 

2

1 10

3 5

Expected Output : 

2

3

5

7

3

5

SOLUTION :

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv)
{
    int t;
    cin>>t;
    while(t--)
    {
        int low,high,i,j,s;
        vector<int> prime;
        cin>>low>>high;
        s=(int)sqrt(high);
        bool hashPrime[s+1];
        memset(hashPrime,true,sizeof(hashPrime));
        bool res[high-low+1];
        memset(res,true,sizeof(res));
        for(i=2;i<=s;++i)
        {
            if(hashPrime[i]==true)
            {
                prime.push_back(i);
                for(j=i*i;j<=s;j+=i)
                {
                    hashPrime[j]=false;
                }
            }
        } 
        for(int i:prime)
        {
            int l=floor(low/i)*i;
            if(l<low) l+=i;
            if(l==i) l+=i;
            for(j=l;j<=high;j+=i)
            {
                res[j-low]=0;
            }
        }
        for(i=0;i<=high-low;++i)
        {
            if(res[i]==1&&i+low!=1)
            {
                cout<<i+low<<"\n";
            }
        }
        cout<<"\n";
    }
    return 0;
}

For Segmented Sieve, Auxiliary Space : O(√n)

For Normal Sieve, Auxiliary Space : O(n)

Never Stop Learning !!