弗拉明戈舞步

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

传说中的「弗拉明戈舞步」是一种在跳的步数为素数时要时拍一下手的神奇舞蹈。现在阿福需要跳 $n$ 步,他想知道自己一共要拍几次手。

PS: 其实上面都是出题人瞎编的。

Input

输入一个整数 $n$ $(1 \leqslant n \leqslant 10^{6})$。

Output

输出 $1$ 到 $n$ 内素数的个数。

Sample Input

3

Sample Output

2

Hint

判断素数可以只判断到 $\sqrt n$。

Source

【2016级ACM暑假集训 结训赛(数据结构组)】bLue