Prime Number

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

素数

6 桁以下の正の整数 n を入力し、n 以下の素数がいくつあるかを出力するプログラムを作成して下さい。ただし、素数とは 1 と自分自身でしか割り切れない正の整数のうち 1 をのぞいたものをいいます。例えば 10 以下の素数は、2, 3, 5, 7 です。

Input

複数のデータセットが与えられます。各データセットに n (1 ≤ n ≤ 999,999) が1行に与えられます。入力の最後まで処理して下さい。

データセットの数は 30 を越えません。

Output

各データセットごとに、n 以下の素数の個数を1行に出力して下さい。

Sample Input

10
3
11

Output for the Sample Input

4
2
5

Source: PC Koshien 2003 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2003
http://www.pref.fukushima.jp/pc-concours/