素数筛法求素数

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