4.4.1　编程实现——统计质数个数

给定一个非负整数n，尝试统计所有小于n的质数的个数。

本题看似简单，实际上暗藏玄机。宇宙间最终极的简单往往也是最高深的复杂，与质数相关的问题就是这样的一种存在。

首先，关于质数我们并不陌生，在之前的章节中，我们也解决过与质数相关的编程题目。对于本题来说，题干非常简单，无非是要找到一定范围内的质数个数。全遍历的思路最直接，我们很容易写出如下代码：

上面的代码理论上虽然可行，但是在实际应用中就不一定可用了。当我们输入的参数n较大时，上面的算法将变得非常耗时。因此，我们需要针对题目要求，更深入地思考质数的性质，来编写出更加高效可用的算法。

本题的核心是将质数筛选出来。在数学上，筛选质数有一种巧妙的方法，即厄拉多塞筛选法。

厄拉多塞是一位古希腊的数学家，关于寻找质数，其发明了一种与众不同的方法。假设我们要寻找100以内的质数，按照厄拉多塞筛选法，首先需要准备一个100个格子的容器分别表示0～99这100个数字。如果某个格子表示的数字为质数，则在这个格子内放入圆球，如果这个格子表示的数字不是质数，则让其空着。初始的时候，我们把除了表示0和1位置之外的盒子都放入圆球，从第3个盒子开始判断，如果2是质数，则将所有表示2的倍数的盒子中的小球都拿走，再继续向后，找到第4个盒子，其表示的数字是3，是质数，因此再将所有表示3的倍数的盒子中的小球拿走，以此类推。最后，所有非空的盒子所表示的数字就是被筛选出来的质数。

根据厄拉多塞筛选法的思路，我们可以改写代码如下：

上面的代码基本是对厄拉多塞筛选法思路的翻译，并且做了一些优化。我们知道偶数一定不是质数，因此在筛选的过程中，跳过了所有的偶数，使用这种算法来筛选质数，可以大大减少需要计算的次数，很大程度上提高了代码的运行效率。