MathSieveNumber Theory
Count the prime numbers that are strictly less than n. Testing each number separately is too slow for large n, so use the Sieve of Eratosthenes.
Input
A single integer n.
Output
Print the number of primes less than n.
Constraints
0 <= n <= 2 * 10^6
Example 1
Input
10
Output
4
The primes below 10 are 2, 3, 5 and 7.