Bertrand's Postulate

Bertrand's postulate states that for every natural number $n$, there exists at least one prime $p$ with $n < p \le 2n$.

The statement was conjectured in 1845 and proved in 1850.

For example, there are 4 primes greater than $10$ and at most $20$: $11, 13, 17, 19$. Likewise, there are 3 primes greater than $14$ and at most $28$: $17, 19, 23$.

Given a natural number $n$, write a program that counts the primes $p$ satisfying $n < p \le 2n$.

The input consists of several test cases. Each case is a single line containing a natural number $n$.

The last line of the input contains $0$; this line is not processed.

For each test case, print on its own line the number of primes $p$ with $n < p \le 2n$.

• $1 \le n \le 123456$