Count Primes in Range
easySave
MathNumber Theory
Given two integers representing the inclusive range [start, end], compute how many numbers within this range are prime numbers. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Example 1
Input
[ 1, 10 ]
Output
4
Explanation. The prime numbers between 1 and 10 are 2, 3, 5, and 7.
Example 2
Input
[ 1, 100 ]
Output
25
Explanation. There are 25 prime numbers between 1 and 100.
Example 3
Input
[ 10, 50 ]
Output
10
Explanation. The prime numbers between 10 and 50 are 11, 13, 17, 19, 23, 29, 31, 37, 41, and 43.
Example 4
Input
[ 100, 200 ]
Output
21
Explanation. There are 21 prime numbers between 100 and 200.
Follow-up: Can you improve the solution to run in less than O(n log log n) time complexity?
Constraints:
- `1 <= start <= end <= 10^6` - You should aim to optimize your solution to handle the upper limit efficiently.
- Views
- 4