Count primes

Given an integer n (0 <= n <= 5e6), return the count of prime numbers strictly less than n. For example for n=10 the primes below it are 2,3,5,7 so the answer is 4. A sieve of Eratosthenes running in O(n log log n) is expected; trial-dividing each number is too slow at the upper bound.