B16 例题-2 埃氏筛求素数

题目描述

利用埃氏筛求出 $n$ 以内的素数。

输入格式

一行一个整数 $n$ ，表示求 $n$ 以内的素数。

输出格式

一行一个整数，表示 $n$ 以内的素数的总数。

样例输入

15

样例输出

6

数据范围

对于$100\%$的数据：$1 \le n\le 10^7$ 。

提示

埃式筛：全称“埃拉托斯特尼筛法”，是一种简单检定素数的打表算法。 要求得自然数 $n$ 以内的全部素数，把小于等于 $\sqrt{n}$ 的所有素数的倍数剔除，剩下的就是素数。