筛法C语言描述求质数之筛法C语言描述
已有259次阅读
200908161020
标签
C语言
质数
素数
快速
筛法
问题描述
试编写一个程序，找出2→N之间的所有质数（质数的概念请看这里），用尽可能快的方法实现。
问题分析
这个问题可以有两种解法：一种是用“筛子法”，另一种是从2→N逐一检测出质数。如果要了解“除余法”，请看另一篇文章《求质数之除余法》。先通过一个简单的例子来介绍一下“筛法”，求2→20的质数，它的做法是先把2→20这些数一字排开：
234567891011121314151617181920
取出数组中最小的数2，把后面2的倍数全部删掉。
235791113151719
接下来取出最小数3，并删除3的倍数。
235711131719
以此类推直至结束，剩余之数皆为素数。
筛法的原理：
1
2
数字2是素数。在数字K前，每找到一个素数，都会删除它的倍数，即以它为因子的整数。如果k未被删除，就表示2k1都不是k的因子，那k自然就是素数了。
算法优化
1
除余法那篇文章里也介绍了，要找出一个数的因子，其实不需要检查2→k，只要从2sqrtk，就可以了。所有，我们筛法里，其实只要筛到sqrt
就已经找出所有的素数了，其中
为要搜索的范围。
f2
另外，我们不难发现，每找到一个素数k，就一次删除2k3k4kik，不免还是有些浪费，因为2k已经在找到素数2的时候删除过了，3k已经在找到素数3的时候删除了。因此，当i＜k时，都已经被前面的素数删除过了，只有那些最小的质因子是k的那些数还未被删除过，所有，就可以直接从kk开始删除。
3
再有，所有的素数中，除了2以外，其他的都是奇数，那么，当i是奇数的时候，ik就是奇数，此时kkik就是个偶数，偶数已经被2删除了，所有我们就可以以2k为单位删除步长，依次删除kkkk2kkk4k。
4
我们都清楚，在前面一小段范围内，素数是比较集中的，比如1→100之间就有25个素数。越到后面就越稀疏。
因为这些素数本身值比较小，所以搜索范围内，大部分数都是它们的倍数，比如搜索1→100，100个数。这光是2的倍数就有50个，3的倍数有33个，5的倍数20个，7的倍数14个。我们只需搜索到7就可以，因此一共做删除操作50332014117次，而2和3两个数就占了83次，这未免太浪费时间了。所以我们考虑，能不能一开始就排除这些小素数的倍数，这里用2和3来做例子。如果仅仅要排除2的倍数，数组里只保存奇数：1、3、5，那数字k的坐标就是k2。如果我们要同时排除2和3的倍数，因为r