ID: 120

Type: Default

1000ms

256MiB

Difficulty: 2

Uploaded By:

Tags>

数组

质数

Description

求 $1,2,\cdots,N$ 中素数的个数。

Format

Input

一行一个整数 $N$ 。

Output

一行一个整数，表示素数的个数。

Samples

Limitation

$1 \le N \le 10^8$ 警告：请使用线性筛解决问题。

In following contests:

[Rated]2025/07/19 新生课前测