By Marcio T. I. Oshiro Brazil
Several mathematical discoveries of the middle ages are due to how famous Arabic mathematicians al-Khwarizmi, Omar Khayyam, and Sharaf al-Din al-Tusi and others. One of the results somewhat unknown is about the hyperprimes numbers. We say that a number is hyperprime if it has a prime number of divisors. Thus, for example, 25 hyperprime is, because it has three dividers. However 42 is not hyperprime, because it has 8 dividers.
Given an integer N, determine the number of hyperprimes in the interval [2, N].
The input consists of several instances and ends with the end of file (EOF).
Each instance consists of a single line containing a single integer N (2 ≤ N ≤ 2 × 106).
For each instance, print a line with the amount of hyperprimes in the interval [2, N].
|Sample Input||Sample Output|