Create a Sieve of Eratosthenes up to the maximum range ie. 106 (or as given in the problem).
Initialise an empty vector ans to store the counts of primes of each query.
After generating the Sieve, count the number of primes up to each index. Iterate through the Sieve and count the number of primes encountered so far.
The Sieve now stores the number of prime numbers up to ‘n’ at that index.
Process each query in the queries input vector.

Extract the left and right range points of the current query.
Calculate the number of primes between the left and right endpoints by substracting the count of primes at index right from the count of primes at index l-1.
Add this count to the answer vector.

Return the ans vector containing counts of primes for each query.

Code

import java.util.*;

class PrimeSieveCounter {

    // Function to generate Sieve of Eratosthenes
    public int[] getSieve(int n) {
        int[] prime = new int[n + 1];
        Arrays.fill(prime, 1); // Assume all numbers are prime
        prime[0] = prime[1] = 0; // 0 and 1 are not prime
import java.util.*;

class PrimeSieveCounter {

    // Function to generate Sieve of Eratosthenes
    public int[] getSieve(int n) {
        int