Count Primes in Range

You are given an upper bound N and then Q queries, each specifying a range [L, R] with 1 <= L <= R <= N. For each query, output the number of prime numbers within that inclusive range. Precompute primality up to N once using a sieve, then answer each query efficiently using prefix sums rather than re-testing primality per query.

Input: The first line contains two integers N and Q. Each of the next Q lines contains two integers L and R describing one query. Output: For each query, print a single integer - the number of primes in the inclusive range [L, R] - on its own line.

1 <= N <= 10^6, 1 <= Q <= 10^5, 1 <= L <= R <= N

Building the sieve and prefix array ONCE upfront (rather than per query) is what makes this efficient at scale - a common mistake is re-running primality checks inside the query loop, which defeats the whole purpose of precomputation.

Precompute which numbers up to N are prime, then answer many range-count queries instantly using prefix sums. Brute force: For every query, check each number in the range for primality directly - this costs O(Q * range size * sqrt(range size)), far too slow when both N and Q can be large. Optimised: Precomputing primality ONCE via a sieve (O(N log log N)) and then building a prefix-count array turns EVERY subsequent query into an O(1) subtraction - since the sieve and prefix array only need to be built once regardless of how many queries follow, this amortizes the upfront cost across potentially many queries.

1. Precompute a boolean SIEVE OF ERATOSTHENES up to N, marking which numbers are composite (once, upfront). 2. Build a PREFIX-COUNT array where prefix[i] = number of primes in [1, i]. 3. Each query [L, R] is then answered in O(1) as prefix[R] - prefix[L-1].

Time: O(N log log N) to build the sieve, plus O(1) per query - O(N log log N + Q) total. Space: O(N), for the sieve and prefix-count arrays.

L can equal R (a single-element range). N=1 means there are no primes at all, so every query answers 0. With N and Q both up to their upper bounds, an O(N log log N) sieve plus O(1)-per-query prefix sums is required for performance.

Be ready to explain the general 'precompute once, answer many queries in O(1)' pattern here - it's a broadly reusable technique whenever the SAME underlying data is queried repeatedly with different ranges.