Count Primes
Medium · math
A prime number is a whole number greater than 1 that has no positive divisors other than 1 and itself.
Given a non-negative integer n, return how many prime numbers are strictly less than n.
For n = 0, n = 1 and n = 2 there are no such primes, so the answer is 0.
Examples
Example 1
Input: n = 10
Output: 4
The primes below 10 are 2, 3, 5 and 7.
Example 2
Input: n = 2
Output: 0
Primes must be strictly less than 2, and there are none.
Example 3
Input: n = 20
Output: 8
The primes below 20 are 2, 3, 5, 7, 11, 13, 17 and 19.
Constraints
- 0 <= n <= 5 * 10^5