图1

如今的孩子可能没怎么见过筛子,传统的筛子样式如同[图1],多是用竹子编织而成,其作用就是通过抖动让细小的东西从筛子下部掉落,而较大的颗粒则留在筛子内,筛子上留的孔洞的大小不同,决定其的应用的地方,这种一次性“留精弃粗”的方式给人们的生活带来的很多的便利(现在有些饮用水过滤机就是利用层层筛网,让自来水成为可供饮用的纯净水)。
那么素数筛又是什么呢?顾名思义,所谓素数筛,“筛”的就是“数”。我回想了一下小学最开始学素数(那时候还有一种说法叫做“质数”,但是就语言上来说,我觉得“素数”这种叫法和“合数”比较搭配,类比于“化学元素”和“化合物”来看,叫“素数”非常贴切)的时候,书上给出的“找素数”的方法,并不是试除法,而是筛选法。所谓筛的过程,用[图2]来展示就很形象:

图2

第一层筛网筛掉所有数字中大于2,且为2的倍数的数字;
第二层筛网筛掉所有数字中大于3,且为3的倍数的数字;
第三层筛网筛掉所有数字中大于5,且为5的倍数的数字;
……

层层筛选之后,我们就可以得到一个范围内的素数表[图3]

 

上图用不同颜色表示筛去的先后顺序及过程,剩余没有被颜色标记的数字就是素数,对于100以内的素数,我们只需要筛取sqrt(100),也就是10以内素数的倍数即可,这个原因和使用试除法只需试除到sqrt(N)的数字是一个道理:

对于正整数N,如果存在不为1的两个正整数p、q,使得p * q = N,则称N为合数
设p <= q
则有p^2 <= p * q = N
即p ^ 2 <= N
所以 p <= sqrt(N)

这就是说,对任意小于或等于sqrt(N)的数字,都不能使N为合数的话,那么N就是一个素数。
素数筛用程序来实现,有各种各样的形式和方法,效率都各有差异,在这里我先使用一种最容易理解的形式,这种形式和上文文字描述是一致的,请看[代码1]

但事实上,我们对照[图3]来看,在筛选素数的过程中,我们由很多重复的操作,比如筛2的时候,我们筛掉了6,但是筛3的时候,我们又一次去筛了6,这样的重复出现了很多次,如果我们能去掉这种重复,那就会取得更好的效果。
下面这段文字建议对照[代码2]阅读,更方便理解。
这次,我们的素数表不再保存偶数,而是只看奇数,也就是数组下标0,代表数字3,下标1代表数字5。而且由筛N内的素数,只需sqrt(N)内的素数这个结论可以知道,对于一个素数P,要筛的下一个数就是P^2,对于我们只存奇数的这种数组而言,就是从 ((i * 2 + 3) ^ 2 – 3) / 2 开始筛选,也就是2 * i ^ 2 + 6 * i + 3,为了减少乘法的次数(现在是三次)以及简化一下式子,我们可以将这个式子部分因式分解一下,也就是我们的初值就是i * (2 * i + 6) + 3(两次乘法,此步纯娱乐行为,看官请随意:))。
确定了第一步,那么接下来怎么筛呢?其实接下来要用到的这个知识,也是我们小学的时候就知道的:

奇数 * 奇数 = 奇数
奇数 * 偶数 = 偶数
奇数 + 偶数 = 奇数
奇数 + 奇数 = 偶数

你说这有什么用呢?第一,我们现在的素数数组,只保存奇数,数组下标和数字的映射关系是num = i * 2 + 3,也就是说,我们下一步要筛掉的,那也必须是个奇数对吧,对于一个已知的素数P而言,第一个要筛掉的之前说过是P^2,P是奇数,所以P^2还是奇数,如果是按照原始版的规则,筛去所有P的倍数,则下一步就是P^2 + P,这个结果是偶数,不用计算也知道,所以干脆我们就每一部加两个P,这样加后的数字就是奇数,转化为下标的映射表示方式,就是下次筛的数字,写做 ((2 * i + 3) ^ 2 + 2 * (2 * i + 3) -3) / 2,也就是2 * i ^ 2 + 8 * i + 6,减去P^2,也就是((2 * i + 3) ^ 2 – 3) / 2,就能得到步进的长度:2 * i + 3,至此,我们的[代码2]也就完成了,使用的时候由于存在一个映射关系,所以之后还附加一个函数,作为判断素数之用:

为了直观的展现以上两种素数判定的方式的速度,我制作了一张图表[图4],显示高数量级内的素数筛选,数量级为2^16 ~ 2^30,每次测试10次,取平均时间,单位为毫秒,精确到0.1。

图4

可以看出,素数筛的时间效率是相当高的,而且经过优化的算法更是能把时间缩短两倍甚至于更多,但是随着筛选范围的增大,用起来可能也不是那么得心应手,对于高数量级范围的素数,我们可以使用“分段筛选”的方法:
素数筛法由于可以由N内的素数筛出N^2内的素数,故在已知2^16内的素数的时候,就可以筛出2^32内的素数,赶紧查一下表,2^16内的素数筛起来是不是就跟玩儿一样的?那么怎么实现分段筛选呢?比如要筛选L ~ R之间的素数,那么你只需要用2 ~ sqrt(R)之间的素数来筛,筛的方法和刚才一模一样,需要注意的就是筛选下界的用法,筛的第一个数的找法应当是:
记TMP = [L / P(素数)](下取整)* P
TMP 是个必定能被P整除的数字,这符合我们筛选的基本原则。
由于有下取整的操作,所以TMP可能会小于下界L,所以如果小于的话就再加一个P,如果使用[代码2]的方式筛选,那么要加P加到TMP为一个奇数的时候才可以。然后就筛吧,效率同样是非常的高,这里代码就不给出了,在POJ有道题目,非常适合作为本篇文章内容的附加练习,请参看[附注2]

[1] 图1 来源自 百度图片
[2] POJ 2689 Prime Distance

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
  Subscribe  
最新 最旧 得票最多
提醒
匿名

int initPrime_f2( )
{
int i, j, T = sqrt((double)N) + 1;
memset(prime, 1, sizeof(prime));
for(i = 3; i <= T; i += 2)
{
if(prime[i / 2])
{
for(j = i * i; j < N; j += i * 2) {
prime[j / 2] = 0;
count++;
}
}
}

int primes = 1;
for(i = 1; i <= N / 2; i ++)
{
if (prime[i])
primes++;
}

return primes;
}