当前没有测试数据。

D - AABCC

得分 : $400$ 分

问题描述

有多少个不大于 $N$ 的正整数可以表示为 $a^2 \times b \times c^2$，其中 $a,b,c$ 是三个质数且满足 $a<b<c$?

约束

• $N$ 是一个整数，满足 $300 \le N \le 10^{12}$。

输入

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

$N$

输出

以整数的形式输出答案。

1000

3

不大于 $1000$ 的符合条件的数有以下三个。

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

1000000000000

2817785