PPractick

The problem

A math-quiz backend gets thousands of questions like "how many primes are there between L and R?", with R up to 10⁶. Testing each number for primality per query repeats the same work over and over. Instead, run the Sieve of Eratosthenes once up to the maximum R, build a prefix count cnt[x] = number of primes ≤ x, and answer every query in O(1) as cnt[R] − cnt[L − 1].

Example: L = 10, R = 20 → 4 (11, 13, 17, 19).

Function signature

vector<int> buildPrimeCounts(int maxN);       // cnt[x] = number of primes <= x
int countPrimes(const vector<int>& cnt, int l, int r);  // 1 <= l <= r <= maxN

Test cases

Input (L, R)	Output	Explanation
(1, 10)	4	2, 3, 5, 7
(10, 20)	4	11, 13, 17, 19
(2, 2)	1
(14, 16)	0
(1, 1000000)	78498	π(10⁶)

(Confirm: 1 is not prime; many queries share the same maximum R, up to about 10⁶–10⁷.)

How interviewers phrase it

• "Given Q queries [L, R], count the primes in each range."
• A single-range version is LeetCode 204 ("count primes less than n").

Clarifying questions to ask

1. How large can R be? (About 10⁶–10⁷ fits a sieve; 10¹² needs a segmented sieve.)
2. How many queries are there?
3. Is the range inclusive at both ends?

Follow-ups to expect

1. "How does the sieve work?"
2. "Why start crossing out at p²?"
3. "Why prefix counts?"
4. "What if R is 10¹² but R − L ≤ 10⁶?"
5. "Complexity?"

Related questions

• Print Prime Factors of a Number Hard
• Prime factorisation of a Number Hard
• Divisors of a Number Easy
• Count all Digits of a Number Easy
• Reverse a number Easy
• Palindrome Number Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in