Prime Counting

Deepjoy is very much fond of prime numbers. He is fascinated by the fact that these numbers are divisible by only 

$2$ numbers ($1$ and the number itself).

His friends challenged him with a problem related to the prime numbers which he eventually cracked.

Now it's your turn to solve the problem. Let's see whether you can solve it or not!

You are given $N$ intervals in the form of $[l_i,r_i]$ (for each valid $i$, where $1\le i\le N$). Each interval contains all the integers $x$ satisfying the condition $x\ge l_i,x\le r_i$. Now find the intersection of all the intervals (integers common to all the intervals) and print the count of the number of primes within the common intersection interval.

Example:

Input:  n = 2, arr = {{2,10},{5,19}}
Output: 2

Approach

C++

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

vector<int> sieve()
{
    bool isPrime[MAX];
    memset(isPrime, true, MAX);

    for (int i = 2; i * i < MAX; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j < MAX; j += i)
                isPrime[j] = false;
        }
    }

    vector<int> prime;
    prime.push_back(2);
    for (int i = 3; i < MAX; i += 2)
    {
        if (isPrime[i])
            prime.push_back(i);
    }
    return prime;
}

void segmentedSieve(int l, int r, vector<int> primes)
{
    bool isPrime[r - l + 1];
    for (int i = 0; i <= r - l; i++)
        isPrime[i] = true;
    for (int i = 0; primes[i] * (long long)primes[i] <= r; i++)
    {
        int currPrime = primes[i];
        long long base = (l / currPrime) * currPrime;
        if (base < l)
            base += currPrime;

        for (long long j = base; j <= r; j += currPrime)
        {
            isPrime[j - l] = false;
        }
        if (base == currPrime)
            isPrime[base - l] = true;
    }
    int ans = 0;
    for (int i = 0; i <= r - l; i++)
    {
        if (isPrime[i])
            ans++;
    }
    if (l == 1)
        ans--;
    cout << ans << endl;
}

void primeCount(int n, vector<vector<int>> &arr)
{
    vector<int> prime = sieve();
    int low = INT_MIN;
    int high = INT_MAX;

    for (int i = 0; i < n; i++)
    {
        int x = arr[i][0], y = arr[i][1];
        low = max(low, x);
        high = min(high, y);
    }
    if (low > high)
        cout << -1 << endl;
    else
        segmentedSieve(low, high, prime);
}
int main()
{

    int n = 2;

    vector<vector<int>> arr = {{2, 10}, {5, 19}};

    primeCount(n, arr);

    return 0;
}