题解

题面描述

给定一个正整数 $n$，要求统计所有不超过 $n$ 的 “漂亮数” 的个数。
这里“漂亮数”的定义为：

• $x$ 为正整数；
• 存在一个质数 $p$ 满足 $x \bmod p = 0$ 且 $p \times p \ge x$。

例如，当 $n=10$ 时，美丽数为 $2,3,4,5,6,7,9,10$，共 $8$ 个。

题目内容

我们定义一个漂亮数是这样的数：

1、该数为正整数

2、设该数为 $x$ ，存在一个质数 $p$ 使得 $x$ $mod$ $p= 0$ 且 $p*p >=x$

给你一个正整数 $n$ ，你能否求出有多少漂亮数小于等于 $n$ ?

输入描述

输入一行一个正整数 $n(1≤n≤5×10^6)$。

输出描述

输出一行一个正整数，代表小于等于 $n$ 的漂亮数的个数。

样例1

输入

10

输出

8