A - 与えられた数より小さい素数の個数について 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

素数とは、1 と自分自身以外に正の約数を持たない、1 以外の自然数のことをいいます。

自然数 n が与えられるので、 n よりも小さい素数の数は何個存在するかを求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
n
  • 自然数 n ( 1 \leq n \leq 10,000 ) が 1 行で与えられる。

出力

n よりも小さい素数の個数を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。

入力例 1

11

出力例 1

4
  • 11 よりも小さい素数は、 2 , 3 , 5 , 7 の 4 つです。
  • ※ 「11 よりも小さい」なので、11 は含みません。

入力例 2

100

出力例 2

25

入力例 3

10000

出力例 3

1229