参考。5由2可知,如果每找到一个素数k,能依次只删除以k为最小素数因子的数,那么每个数字就都只被删除一次,那这个筛法就能达到线性的O
效率了。比如数字600223511,其中2是它的最小素数因子。那这个数就被2删除了。3、5、11虽然都是它的因子,但不做删除它的操作。要实现这种策略,那每找到一个素数k,那从k开始,一次后面未被删除的数字来与k相乘,删除它们的积。比如要筛出2~60之间的素数:1先列出所有的数。
02030405060708091011121314155051525354555657585960
2选出序列中的第一个数2,判定它是素数,然后从2开始,依次与剩下的未被删除的数相乘,删除它们的积。224,236,即248。
02030405060708091011121314155051525354555657585960020305070911131517192123252729313335373941434547495153555759
3去掉2后,再选出序列中第一个数3,判定它是素数,然后从3开始,依次与剩下的数相乘,即339,3515,3721
020305070911131517192123252729313335373941434547495153555759020305071113171923252931353741434749535559
f4去掉3后,选出最小的数5,判定它为素数,依次删除5525,5735,51155,
020305071113171923252931353741434749535559020305071113171923293137414347495359
5去掉5后,选出最小的数7,为素数,删除7749,
0203050711131719232931374143474953590203050711131719232931374143475359
6去掉7后,第一个数11的平方121大于60,所以结束。剩下的数字全为素数。
0203050711131719232931374143475359
上面的操作效率很高,但在计算机中模拟的时候却又很大的障碍:首先,计算机内存是一维的空间,很多时候我们不能随心所欲,要实现上面的算法,要求这个数据结构既能很高效地查找某个特定的值,又能不费太大代价对序列中的元素进行删除。高效地查找,用数组是最合适的了,能在O1的时间内对内存进行读写,但要删除序列中一个元素却要O
;单链表可以用O1的时间做删除操作,当然要查找就只能是O
了。所以这个数据结构很难找。其次,筛法的一个缺点就是空间浪费太大,典型的以空间换时间。如果我们对数组进行压缩,比如初始时就排除了所有偶数,数组0对应数字1,1对应3,。这样又会因为多了一道计算数字下标的工序而浪费时间。这又是一个矛盾的问题。
f也许我们可以试试折中的办法:数据结构综合数组和链表2种,数组用来做映射记录,链表来记录剩下的还r