241. Primes Below N
A radio-astronomy team tags every signal channel with a positive integer and only keeps channels whose tag is a prime number. Given the integer n, return how many prime numbers are strictly smaller than n.
For example, if n is 3 the only prime below it is 2, so the answer is 1; for n = 0, 1 or 2 the answer is 0. A prime is an integer greater than 1 whose only positive divisors are 1 and itself. Testing every number one by one is too slow for the largest inputs: aim for a sieve that runs in about O(n log log n) time using O(n) memory.
Example 1
- Input:
- n = 47
- Output:
- 14
- Explanation:
The primes below 47 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 and 43, fourteen in total.
Example 2
- Input:
- n = 211
- Output:
- 46
- Explanation:
There are 46 primes strictly less than 211, and 211 itself is not counted.
Constraints
0 ≤ n ≤ 5 * 106. The answer always fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log log n)
- Space
- O(n)