Count primes below n

Return the number of prime numbers strictly less than a given non-negative integer n. For example, there are 4 primes below 10 (2, 3, 5, 7). n can be up to 5,000,000. Aim for a solution that runs well within a few seconds at the upper bound.