Problem

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.

Formal Specification

• Input: An integer n
• Output: An integer representing the number of primes in the range [0, n)

Examples

Example 1

• Input: n = 10
• Output: 4
• Explanation: The primes less than 10 are 2, 3, 5, 7.

Example 2

• Input: n = 0
• Output: 0
• Explanation: There are no positive integers less than 0, so there are no primes.

Example 3

• Input: n = 2
• Output: 0
• Explanation: 2 is not counted because the range is strictly less than n.

Constraints

• 0 <= n <= 5 * 10^6
• Your solution should be efficient enough for large values of n
• Return the count, not the list of primes