题目描述
质数，即大于 $1$ 的，除了 $1$ 和本身之外不能被其他自然数整除的数。
- 33DAI 喜欢质数，对于一个质数 $x$ 来说，$2\sim (x-1)$ 之间一个因子也没有，非常安静。
- 与之相对，33DAI 认为一个数 $x$ 如果在 $2\sim (x-1)$ 之间**有且只有两个因子**。那么这就是一个**喧闹数**。
现在 33DAI 想要消灭 $1\sim n$ 以内的所有喧闹数。请你帮他数数，一共有几个。
输入
一个数 $n$。
输出
输出 $1\sim n$ 之内有几个喧闹数。
样例输入输出
提示
对于 $100\%$ 的数据，$1 \le n \le 10^7$。
- 子任务 1（10 分）：$n=50$
- 子任务 2（20 分）：$n\le 10^5$
- 子任务 3（30 分）：$n=3333333$
- 子任务 4（40 分）：没有特殊限制