SegmentedSieve.cpp

#include<bits/stdc++.h>
using namespace std;
#define M 32000   // sqrt(10^9)
vector<int> prime;

    void segmentedSieve(long long l, long long r)
    {
        bool primeNumbers[r-l + 1];
        memset(primeNumbers, true , sizeof(primeNumbers));
        if(l == 1) primeNumbers[0] = false;
        for(int i = 0; prime[i]*prime[i] <= r; ++i)    //taking the prime numbers from the vector
        {
            int currentPrime = prime[i];
            long long temp = (l/currentPrime)*currentPrime;
            if(temp < l) temp += currentPrime;
            for( long long j = temp; j <= r; j += currentPrime)
            {
                primeNumbers[j-l] = false;
            }
            if(temp == currentPrime) primeNumbers[temp - l] = true;
        }

for (int i = 0; i < r - l + 1; ++i) {
        if (primeNumbers[i]) cout << (i+l) << endl;
    }
    }
// finding the prime numbers within 1 to 32000
    void sieve()
    {
        bool primeNumbers[M];
        memset(primeNumbers, true , sizeof(primeNumbers)); // keeping boolean true in every index

        for(int i = 3; i*i <= M; i += 2)
        {
            if(primeNumbers[i])
            {
              for(int j = i*i; j <= M; j += i)
              {
                  primeNumbers[j] = false;
              }
            }
        }

        prime.push_back(2);
        for(int i = 3; i <= M; i +=2 )
        {
            if(primeNumbers[i]) prime.push_back(i);
        }
       // printing prime numbers for testing
       // for(int i = 0; i <= 50; ++i)  cout<< i << " " << (primeNumbers[i] ? "prime" : "not prime") << endl;
       // cout<<prime[i]<<endl;
    }

    int main()
    {
        sieve();
        int T;
        cin>>T;
        while(T--)
        {
          long long left,right;
          cin>>left>>right;
          segmentedSieve(left,right);
        }
    }