AT_abc250_d [ABC250D] 250-like Number

题目描述

满足以下条件的整数 $k$ 被称为“250 类似数”。

• 存在素数 $p < q$，使得 $k = p \times q^3$。

请问不超过 $N$ 的“250 类似数”共有多少个？

输入格式

输入为以下格式，从标准输入读取。

$N$

输出格式

请输出答案，结果为一个整数。

输入输出样例 #1

输入 #1

250

输出 #1

2

输入输出样例 #2

输入 #2

1

输出 #2

0

输入输出样例 #3

输入 #3

123456789012345

输出 #3

226863

说明/提示

限制条件

• $N$ 是一个满足 $1 \leq N \leq 10^{18}$ 的整数。

样例解释 1

• $54 = 2 \times 3^3$，因此是“250 类似数”。
• $250 = 2 \times 5^3$，因此是“250 类似数”。 不超过 $250$ 的“250 类似数”有上述 $2$ 个。

由 ChatGPT 4.1 翻译