Range Prime Count — Solution & Editorial

Back to the Problem

Precompute a prefix count of the predicate; each query is a subtraction.

Complexity: O(N + Q)