Sieve Range Prime Density
medium
MathNumber TheoryCountingSieve Of Eratosthenes
Asked atGoogleMicrosoftAmazon
Problem Description
You are given two non-negative integers `lo` and `hi`. Return the **count of prime numbers** in the inclusive range [lo, hi].
A prime number is a natural number greater than 1 whose only divisors are 1 and itself.
**Example 1:**
```
Input: lo = 10, hi = 30
Output: 6
Explanation: Primes in [10, 30]: {11, 13, 17, 19, 23, 29} → 6 primes.
```
**Example 2:**
```
Input: lo = 0, hi = 6
Output: 3
Explanation: Primes in [0, 6]: {2, 3, 5} → 3 primes.
```
Constraints
- 0 <= lo <= hi <= 10^6
Follow-up
Can you solve this using a segmented sieve in O((hi-lo) log log hi) space when lo and hi can be up to 10^12?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.