Bertrand's postulate (Bertrand-Chebyshev theorem, Chebyshev theorem) states that for any \(n > 1\) there is a prime number p in the interval \(n < p < 2n\). Such a conjecture was put forward in 1845 by the French mathematician Joseph Bertrand (who checked it up to \(n=3000000\)) and proved in 1850 by Pafnuty Chebyshev. Ramanuzhan in 1920 found a simpler proof, and Erdős in 1932 – even simpler.
Your task is to solve a somewhat more general – namely, by the number n find the number of prime numbers p from the interval \(n < p < 2n\).
Recall that a number is called prime if it is only divisible by itself and one
Input
Integer n (\(2 <= n <= 50000\)).
Imprint
Print one number – answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
3000 |
353 |