筛法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