消灭喧闹数

题目描述

质数，即大于 $1$的，除了 $1$和本身之外不能被其他自然数整除的数。

小珅喜欢质数，对于一个质数 $x$来说，$2 \sim (x - 1)$之间一个因子也没有，非常安静。

与之相对，小珅认为一个数 $x$如果在 $2 \sim (x - 1)$之间有且只有两个因子，那么这就是一个喧闹数。

现在小珅想要消灭 $1 \sim n$以内的所有喧闹数。请你帮他数数，一共有几个。

输入格式

一个数 $n$。

输出格式

输出 $1 \sim n$之内有几个喧闹数。

输入输出样例

输入 #1

33

输出 #1

10

输入 #2

333

输出 #2

102

输入 #3

33333

输出 #3

8204

输入 #4

6666666

输出 #4

1290301

说明/提示

对于 $100\%$的数据，$1 \le n \le 10^7$。

子任务 $1$（$10$分）：$n = 50$。

子任务 $2$（$20$分）：$n \le 10^5$。

子任务 $3$（$30$分）：$n = 3333333$。

子任务 $4$（$40$分）：没有特殊限制。