Count Primes

Given an integer \(n\), count the number of prime numbers strictly less than \(n\). A prime number is a number greater than 1 that has no positive divisors other than 1 and itself.

You are required to read the input from stdin and output the result to stdout.

Note: For an integer \(n\), the answer is the number of primes \(p\) such that \(2 \leq p < n\).

inputFormat

The input consists of a single line containing an integer \(n\) (\(0 \le n \le 10^6\)).

outputFormat

Output a single integer representing the number of prime numbers less than \(n\).

10

4