题目描述

输入一个整数 $n$，请问 $1 \sim n$ 范围内有多少个素数？

素数（也叫质数）是指大于 $1$ 的自然数，且除了 $1$ 和它自身外，不能被其他自然数整除的数。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示 $1 \sim n$ 范围内素数的个数。

样例

20

8

样例解释
$1$ 到 $20$ 之间的素数依次为 $2, 3, 5, 7, 11, 13, 17, 19$，共 $8$ 个，因此输出 $8$。

数据范围

• $n \le 10^7$