Score : $400$ points

问题陈述

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

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

How many positive integers no greater than $N$ can be represented as $a^2 \times b \times c^2$ with three primes $a,b$, and $c$ such that $a<b<c$?

Constraints

• $N$ is an integer satisfying $300 \le N \le 10^{12}$.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print the answer as an integer.

Sample Input 1

1000

Sample Output 1

3

The conforming integers no greater than $1000$ are the following three.

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

Sample Input 2

1000000000000

Sample Output 2

2817785

update @ 2024/3/10 08:24:17