漂亮数

题目描述

我们定义一个正整数 $x$ 是“漂亮数”，当且仅当它同时满足以下两个条件：

1. $x$ 是一个正整数。
2. 存在一个质数 $p$，使得 $x$ 是 $p$ 的倍数，且 $p^2 \ge x$。
   • 形式化地，存在质数 $p$ 满足 $x \pmod p = 0$ 且 $p \times p \ge x$。

给定一个正整数 $n$，请你计算有多少个小于等于 $n$ 的正整数是“漂亮数”。

输入格式

输入一行，包含一个正整数 $n$。

输出格式

输出一行，包含一个正整数，表示小于等于 $n$ 的“漂亮数”的数量。

样例

样例输入

10

样例输出

8

提示

样例说明

在 $1$ 到 $10$ 的整数中：

• $1$ 不是漂亮数，因为它没有质数因子。
• $8$ 不是漂亮数。它唯一的质数因子是 $p=2$。虽然 $8 \pmod 2 = 0$，但是 $2 \times 2 = 4 < 8$，不满足 $p \times p \ge x$ 的条件。
• 其他数都是漂亮数。例如，对于 $x=6$，它的质因子有 $2$ 和 $3$。
  • 若选择 $p=2$，则 $2 \times 2 = 4 < 6$，不满足。
  • 若选择 $p=3$，则 $3 \times 3 = 9 \ge 6$，满足条件。因此 $6$ 是漂亮数。
• 小于等于 $10$ 的漂亮数有 $\{2, 3, 4, 5, 6, 7, 9, 10\}$，共 $8$ 个。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 < n \le 5 \times 10^6$