解题思路

要统计的是严格小于 $n$ 的质数，所以筛的范围是 $0$ 到 $n-1$ ， $n$ 本身不进入筛表。

$n<2$ 时直接返回 $0$ 。否则用埃氏筛：从 $2$ 开始，凡是还没被划掉的数就是质数，再把它的倍数全部划掉。倍数从 $i^2$ 开始即可，更小的倍数已经被更小的质数划过。

题目内容

给定一个非负整数 $n$ ，统计所有严格小于 $n$ 的质数个数。质数是大于 $1$ 、且只能被 $1$ 和自身整除的正整数。 $n$ 本身即使是质数也不计入。不存在这样的质数时，答案是 $0$ 。

一行一个整数 $n$ 。

$0 \le n \le 10^6$

输出一个整数，表示严格小于 $n$ 的质数个数。

输入

输出

说明

严格小于 $10$ 的质数是 $2$ 、 $3$ 、 $5$ 、 $7$ ，一共 $4$ 个。

输入

输出

说明

小于 $0$ 的正整数不存在，答案是 $0$ 。

输入

输出

说明

严格小于 $2$ 的整数里没有质数。 $2$ 本身不计入。

选择提交后点击「开始AI分析」