Count primes in range L to R
HardSieve of Eratosthenes, then count
Problem
Count how many prime numbers lie between L and R inclusive.
Sieve out non-primes up to R, then count the primes that fall in [L, R].
The idea
Mark every multiple of each prime as composite up to R, then count the survivors between L and R. Sieving once costs O(R log log R), far less than testing each number in the range individually.
The trick
- Start marking at p·p — smaller multiples already have a smaller prime factor.
- For a large R with a narrow range, use a segmented sieve.
- A prefix-count array answers many range queries in O(1) each.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — L=10, R=20 Values: 10, 20.
1sieve of Eratosthenes up to R2count primes with L <= p <= RInput
- array
- [10, 20]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 7
- Output:
- true
- Explanation:
- 7 has no divisors other than 1 and 7.
Example 2
- Input:
- n = 12
- Output:
- false
- Explanation:
- 12 = 3 x 4, so it has extra divisors.
Example 3
- Input:
- n = 1
- Output:
- false
- Explanation:
- 1 is not considered prime.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.