AT_abc300_d [ABC300D] AABCC

题目描述

在不超过 $N$ 的正整数中，有多少个可以表示为 $a^2 \times b \times c^2$ 的数，其中 $a, b, c$ 均为素数，且满足 $a < b < c$？

输入格式

输入从标准输入中给出，格式如下：

$N$

输出格式

请输出满足条件的整数的个数。

输入输出样例 #1

输入 #1

1000

输出 #1

3

输入输出样例 #2

输入 #2

1000000000000

输出 #2

2817785

说明/提示

限制条件

• $N$ 是满足 $300 \leq N \leq 10^{12}$ 的整数。

样例说明 1

不超过 $1000$ 且满足条件的整数有以下 $3$ 个：

• $300 = 2^2 \times 3 \times 5^2$
• $588 = 2^2 \times 3 \times 7^2$
• $980 = 2^2 \times 5 \times 7^2$

由 ChatGPT 4.1 翻译