In a Google Play mobile performance utility, you need a fast way to answer a simple math-based query: given an integer n, return how many prime numbers are strictly less than n.
A prime number is an integer greater than 1 with exactly two positive divisors: 1 and itself.
n[0, n)Example 1
n = 10410 are 2, 3, 5, 7.Example 2
n = 000, so there are no primes.Example 3
n = 202 is not counted because the range is strictly less than n.0 <= n <= 5 * 10^6nn = 10Output4WhyThe prime numbers less than 10 are 2, 3, 5, and 7.n = 2Output0WhyThere are no prime numbers strictly less than 2.n = 20Output8WhyThe primes less than 20 are 2, 3, 5, 7, 11, 13, 17, and 19.0 <= n <= 5 * 10^6Input is a single integerReturn the number of primes strictly less than ndef count_primes(n):
