2778: T3-遣其欲，而心自静
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
质数，即大于 $1$ 的，除了 $1$ 和本身之外不能被其他自然数整除的数。
- 33DAI 喜欢质数，对于一个质数 $x$ 来说，$2\sim (x-1)$ 之间一个因子也没有，非常安静。
- 与之相对，33DAI 认为一个数 $x$ 如果在 $2\sim (x-1)$ 之间**有且只有两个因子**。那么这就是一个**喧闹数**。
现在 33DAI 想要消灭 $1\sim n$ 以内的所有喧闹数。请你帮他数数，一共有几个。
- 33DAI 喜欢质数，对于一个质数 $x$ 来说，$2\sim (x-1)$ 之间一个因子也没有，非常安静。
- 与之相对，33DAI 认为一个数 $x$ 如果在 $2\sim (x-1)$ 之间**有且只有两个因子**。那么这就是一个**喧闹数**。
现在 33DAI 想要消灭 $1\sim n$ 以内的所有喧闹数。请你帮他数数，一共有几个。
输入
一个数 $n$。
输出
输出 $1\sim n$ 之内有几个喧闹数。
样例输入 复制
33样例输出 复制
10提示
```input2
333
```
```output2
102
```
```input3
33333
```
```output3
8204
```
```input4
6666666
```
```output4
1290301
```
样例不解释，自己打表。
## 数据规模与约定
对于 $100\%$ 的数据，$1 \le n \le 10^7$。
- 子任务 1（10 分）：$n=50$
- 子任务 2（20 分）：$n\le 10^5$
- 子任务 3（30 分）：$n=3333333$
- 子任务 4（40 分）：没有特殊限制
333
```
```output2
102
```
```input3
33333
```
```output3
8204
```
```input4
6666666
```
```output4
1290301
```
样例不解释，自己打表。
## 数据规模与约定
对于 $100\%$ 的数据，$1 \le n \le 10^7$。
- 子任务 1（10 分）：$n=50$
- 子任务 2（20 分）：$n\le 10^5$
- 子任务 3（30 分）：$n=3333333$
- 子任务 4（40 分）：没有特殊限制