3862: 遣其欲，而心自静(挖土机 CSP-J 模拟赛 ~ 第三场)

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：1

题目描述

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

  • 33DAI 喜欢质数，对于一个质数 � 来说，2∼(�−1) 之间一个因子也没有，非常安静。
  • 与之相对，33DAI 认为一个数 � 如果在 2∼(�−1) 之间有且只有两个因子。那么这就是一个喧闹数。

现在 33DAI 想要消灭 1∼� 以内的所有喧闹数。请你帮他数数，一共有几个。

输入

一个数 �。

输出

输出 1∼� 之内有几个喧闹数。

样例输入 复制 

33

样例输出 复制 

10

提示


数据规模与约定

对于 100% 的数据，1≤�≤107。

  • 子任务 1（10 分）：�=50
  • 子任务 2（20 分）：�≤105
  • 子任务 3（30 分）：�=3333333
  • 子任务 4（40 分）：没有特殊限制

来源/分类

提交提交记录统计露一手!