Score : $400$ points

问题描述

让我们认为一个整数 $k$ 如果满足以下条件，则称其“类似于 250”：

• 将 $k$ 表示为 $k=p \times q^3$，其中 $p$ 和 $q$ 为小于 $q$ 的质数。

在不大于 $N$ 的整数中有多少个是“类似于 250”的？

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

Problem Statement

Let us regard an integer $k$ as "similar to $250$" if the following condition is satisfied:

• $k$ is represented as $k=p \times q^3$ with primes $p<q$.

How many integers less than or equal to $N$ are "similar to $250$"?

Constraints

• $N$ is an integer between $1$ and $10^{18}$ (inclusive)

Input

Input is given from Standard Input in the following format:

$N$

Output

Print the answer as an integer.

Sample Input 1

250

Sample Output 1

2

• $54 = 2 \times 3^3$ is "similar to $250$".
• $250 = 2 \times 5^3$ is "similar to $250$".

The two integers above are all the integers "similar to $250$".

Sample Input 2

1

Sample Output 2

0

Sample Input 3

123456789012345

Sample Output 3

226863

update @ 2024/3/10 10:41:11