题目描述

给定一个正整数$n$，请输出$1 - n$中素数的个数。

样例输入

输入仅一行一个正整数$n$。

样例输出

输出素数的个数。

样例

样例一

3

2

数据范围

本题一共$20$个测试点，用于大家比较不同素数筛在不同数量级的速度。

$1 - 5$个测试点$1 \le n \le 10^{5}$

$6 - 10$个测试点$1 \le n \le 10^{6}$

$11 - 15$个测试点$1 \le n \le 10^{7}$

$16 - 20$个测试点$1 \le n \le 10^{8}$