204 统计小于n的质数的个数（埃氏筛法、欧拉筛法）
|
一、题目
二、数学基础 1. 质数是除了1和它本身之外，不能被其他数整除的正整数，又称素数。比如：2,3,5,7,11... 4. 合数可以表示成几个质数相乘的形式。
三、分析 题目很容易理解。 最容易想到的方法就是根据定义，把从2到n-1的数挨个进行判断是不是质数。判断x的时候，还要套一层循环。这样做效率太低。
四、方法一：埃氏筛 埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由古希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。
开心时刻： 我做题的时候在网上看到一个方法叫厄拉多塞筛法，发现跟埃氏筛法方法一样。于是很迷惑，同样一个方法怎么由两个人提出呢。。然后就觉得这两个方法肯定有哪个地方不一样，肯定是我没有看清楚。。直到我突然想到这种可能： 【方法】 方法如下： 要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
【原理】 我们先用一个简单的方法来做。比如我们要求26以内的素数。我们用黑色表示素数，红色表示非素数。 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第一步，2为素数。2的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第二步，3为素数。3的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第三步，5为素数。5的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第四步，7为素数。7的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第五步，11为素数。7的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第六步，13为素数。7的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第七步，17为素数。7的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第八步，19为素数。7的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第九步，23为素数。7的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 至此，合数全部划掉了，剩下的全是素数。
改进一： 其实都不需要到23，到5就足够了。即到根号25即可。为什么呢？ 因为当i为大于5的素数时，i*i>25。对于i*2，i*3，...，i*k，... 等在(i+1, 25)之间的数。k都小于i。这些数并不需要i来筛，因为k就把他们筛掉了。（若k为质数，则由k筛掉。若k为合数，k可以分解为更小的两个质数的乘积，这些数由这些质数筛掉）。 比如，7的2倍为14。7*2 = 14，14已经由2筛掉了，不需要7来筛。7*3 = 21，21由3筛掉了，不要有由7来筛。
这样改进之后就是埃氏筛法。把不大于根号n的所有素数的倍数剔除，剩下的就是素数。所以上面的例子为： 第一步，2为素数。2<5。2的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第二步，3为素数。3<5。3的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第三步，5为素数。5<=5。5的倍数的全部标为合数。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 下一个元素为7>5。停止。
改进二： 其实还可以改进一下。就是在筛i的倍数的时候，不必从i的二倍开始筛，直接从i*i开始筛即可。原因跟上面一样。对于i*2，i*3， i*k，...等小于i*i的数，k已经筛过了，不需要i来筛。所以，上面的例子为： 第一步，2为素数。2<5。从4开始筛。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第二步，3为素数。3<5。从9开始筛。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 第三步，5为素数。5<=5。从25开始筛。2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 下一个元素为7>5。停止。
【代码】
【结果】
其实效果已经很好了。因为再靠前的算法是这样的：
简直是搞笑。。。这种牛人比不过。。。
【总结】 埃式筛法很容易理解，并且在效率上也比较优秀，时间复杂度为O(nlglgn)，即O(nloglogn)。 但是在处理1e8以上的数据时，还是稍稍力不从心，所以接下来我们着重介绍下线性时间筛法——欧拉筛法
五、方法二：欧拉筛法
上面的埃氏筛法虽然已经够好了，但是还是有问题，比如12被2筛了一遍，又被3筛了一遍。怎么才能让一个数只被筛一遍呢？我们做进一步分析。
假设n为100，我们刚才的做法是： 对于素数2：筛掉了他的2倍，3倍，4倍，5倍，6倍，7倍，8倍，9倍，10倍，11倍，12倍....49倍。 对于素数3：筛掉了他的 3倍，4倍，5倍，6倍，7倍，8倍，9倍，10倍，11倍，12倍....33倍。 对于素数5：筛掉了他的 5倍，6倍，7倍，8倍，9倍，10倍，11倍，12倍....19倍。 对于素数7：筛掉了他的 7倍，8倍，9倍，10倍，11倍，12倍....14倍。
我们换一个角度想。使用prime数组保存当前已经找到的素数。i为倍数。 筛掉了它的2倍的素数有： //i=2 prime=[2] 2 //4 筛掉了它的3倍的素数有： //i=3 prime=[2,3] 2 //6 3 //9 筛掉了它的4倍的素数有： //i=4 prime=[2,3] 2 //8 3 //12 筛掉了它的5倍的素数有： //i=5 prime=[2,3,5] 2 //10 3 //15 5 //25 筛掉了它的6倍的素数有： //i=6 prime = [2,3,5] 2 //12 3 //18 5 //30 筛掉了它的7倍的素数有： //i=7 prime=[2,3,5,7] 2 //14 3 //21 5 //35 7 //49 筛掉了它的8倍的素数有： //i=8 prime=[2,3,5,7] 2 //16 3 //24 5 //40 7 //56 筛掉了它的9倍的素数有： //i=9 prime=[2,3,5,7] 2 //18 3 //27 5 //45 7 //63 .........
我们注意到当i=4时，被3筛掉了一遍12。当i=6时，被2又筛掉了一遍12。导致重复筛除。再比如当i=6时，30被5筛掉了一次，后面i=15时，肯定还会被2再筛掉一次。我们想只筛一遍，怎么筛呢？ 我们希望一个合数被它最小的素数筛掉，这样就能保证每个数被筛一遍。比如，12只想被2筛掉。我们想简化成如下：
筛掉了它的2倍的素数有： //i=2 prime=[2] 2 //4 筛掉了它的3倍的素数有： //i=3 prime=[2,3] 2 //6 3 //9 筛掉了它的4倍的素数有： //i=4 prime=[2,3] 2 //8 筛掉了它的5倍的素数有： //i=5 prime=[2,3,5] 2 //10 3 //15 5 //25 筛掉了它的6倍的素数有： //i=6 prime = [2,3,5] 2 //12 筛掉了它的7倍的素数有： //i=7 prime=[2,3,5,7] 2 //14 3 //21 5 //35 7 //49 筛掉了它的8倍的素数有： //i=8 prime=[2,3,5,7] 2 //16 筛掉了它的9倍的素数有： //i=9 prime=[2,3,5,7] 2 //18 3 //27 .........
是怎么简化的呢？ 方法就是：当i%prime[j] == 0 时，就不再考虑prime[j+1]及以后的了。比如，当i=8时，prime=[2,3,5,7]。本来是要筛掉2的8倍，3的8倍，5的8倍，7的8倍。但是8%2==0，所以2后面的3,5,7就不考虑了。
为什么呢？我们来证明一下： 当i%prime[j]==0时，i是prime[j]的倍数。比如：i = k* prime[j]。对于下一个要筛掉的数字：i*prime[j+1]就可以写成k*prime[j]*prime[j+1]。而prime[j]<prime[j+1]，所以i*prime[j+1]可以留到后面被 prime[j]筛掉，这里就不用筛掉了。后面的数字i*prime[j+2], i*prime[j+3]等也是一样。 举例来说：当i=8时,prime=[2,3,5,7]。i=2，筛掉了16。这时候判断8是2的倍数，所以就不筛3,5,7的8倍了。为什么不筛3的8倍呢?因为8是2的倍数，3的8倍肯定是2的倍数。2又小于3，所以要后面留给2筛。
这就是欧拉筛法最关键的地方。就一句话：if(i%prime[j]==0) break;
【代码】
【结果】
【分析】 效果没有埃氏筛法好，原因并不是算法不好，而是n比较小，体现不出优势。建立prime[]数组等又花费了一些时间，导致效果不好。 我们来验证一下。 编写以下代码：
埃氏筛法的代码跟前面往前相同，欧拉筛法的代码改动了一个地方： 因为当n很大的时候，质数是非常少的。不需要用那么多空间来存储。
测试一：n为1*10^6时，得到的结果如下： 说明：数据量不是很大时，埃氏筛法较快。因为欧拉筛法要申请空间等，占用了一些时间。
测试二：n为1*10^7时，结果如下：
还是埃氏筛法快一点。
测试三：n为1*10^8时，结果如下： 说明，n很大时，欧拉筛法的优势开始体现出来了。
|