Count Primes in Range — Solution & Editorial

Back to the Problem

Precompute prefix counts of the predicate; each query is pre[r] − pre[l−1] in O(1).

Complexity: O(N + Q)