登陆注册
57676100000018

第18章 埃拉托斯特尼筛法

给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去......。

详细列出算法如下:

列出2以后的所有序列:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

标出序列中的第一个素数,也就是2,序列变成:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

将剩下序列中,划掉2的倍数,序列变成:

2 3 5 7 9 11 13 15 17 19 21 23 25

如果这个序列中最大数小于最后一个标出的素数的平方,那么剩下的序列中所有的数都是素数,否则回到第二步。

本例中,因为25大于2的平方,我们返回第二步:

剩下的序列中第一个素数是3,将主序列中3的倍数划掉,主序列变成:

2 3 5 7 11 13 17 19 23 25

我们得到的素数有:2,3

25仍然大于3的平方,所以我们还要返回第二步:

序列中第一个素数是5,同样将序列中5的倍数划掉,主序列成了:

2 3 5 7 11 13 17 19 23

我们得到的素数有:2,3,5 。

因为23小于5的平方,跳出循环.

结论:2到25之间的素数是:2 3 5 7 11 13 17 19 23。

同类推荐
  • 北漠含烟

    北漠含烟

    古烟儿替杜北漠填好的志愿,被杜亚安,杜北漠的父亲悄悄的改了。两个人因此互相误会。父母眼中为子女的好,有时候是会毁了两个人的人生。古烟儿经历了悲惨的童年人生,改过三次姓名,住在养父母家,8岁姥姥去世被还回去,后来又回到养父母家。更加因为杜爸爸的这一举措颠沛流离了大半生。古烟儿陪伴杜北漠五年时间,杜北漠以为古烟儿在他心里扎了根,但她却入了他的肺。互相过于懂对方,有时候也会是两个人分开的原因。
  • 悠闲重生路

    悠闲重生路

    重生后,他本来只想悠闲于世,做一个无忧无虑的重生者,可是他注定是要走上巅峰的男人!
  • 父母不在身边的日子

    父母不在身边的日子

    多年来,这些被丢在“空巢”中的儿童,有的因亲情缺失、监管乏力而导致的人身伤亡和失足犯罪,一幕幕悲剧叫人痛心疾首。也有的孩子在面对逆境和贫困,却选择了挺起幼弱的身躯拼力抗争。留守儿童的故事很多,有一件一件令人深思的,也有一件一件感人至深的。我希望通过不同的故事想全社会传递出一个信息:这个群体应该得到更多的关爱和重视……
  • 小学的真相

    小学的真相

    原以为小学校园是片欢喜净土,谁曾想,看似平静的表面下,波涛汹涌,暗礁丛生,迷糊小大佬乘坐的小船如何乘风破浪,扬帆起航?
  • 石朵儿

    石朵儿

    世界很大,却无家可归,这也许就是最寂寞的事。
热门推荐
  • 美女主播爱上我

    美女主播爱上我

    一个县级电视台的屌丝记者,女友与他分手,他因为失恋,失魂落魄,走在大街上遭遇车祸,昏迷三天三夜。抢救过来以后,拥有读心超能力和超强功夫。从此,他驰骋职场,玩转都市,美女主播、美女同事、各种美女接踵而至爱上他,职场平步青云,年纪轻轻,混成电视台副台长、台长……
  • 执子之手与子偕老:忆江南

    执子之手与子偕老:忆江南

    死生挈阔与子成说执子之手与子偕老有些爱,是藏在心底的。
  • 现代妖事怪谈

    现代妖事怪谈

    一个生意冷清的小书店,一个不起眼的书店老板。身处常人眼中鬼魅魍魉的世界。在城市与人心的幽暗处行走。超脱常识之外,冷眼旁观。想知道漫漫岁月中,有多少痛苦哀伤隐藏?那些看不到的角落,到底是何等离奇,请来到虚空的世界,一窥那些幽冥之物。
  • 天行

    天行

    号称“北辰骑神”的天才玩家以自创的“牧马冲锋流”战术击败了国服第一弓手北冥雪,被誉为天纵战榜第一骑士的他,却受到小人排挤,最终离开了效力已久的银狐俱乐部。是沉沦,还是再次崛起?恰逢其时,月恒集团第四款游戏“天行”正式上线,虚拟世界再起风云!
  • 贪恋红尘三千尺

    贪恋红尘三千尺

    本是青灯不归客,却因浊酒恋红尘。人有生老三千疾,唯有相思不可医。佛曰:缘来缘去,皆是天意;缘深缘浅,皆是宿命。她本是出家女,一心只想着远离凡尘逍遥自在。不曾想有朝一日唯一的一次下山随手救下一人竟是改变自己的一生。而她与他的相识,不过是为了印证,相识只是孽缘一场。
  • 瑶城之恋

    瑶城之恋

    花朵离不开太阳倾心离不开他因为他是我的光我们都一样……
  • 天行

    天行

    号称“北辰骑神”的天才玩家以自创的“牧马冲锋流”战术击败了国服第一弓手北冥雪,被誉为天纵战榜第一骑士的他,却受到小人排挤,最终离开了效力已久的银狐俱乐部。是沉沦,还是再次崛起?恰逢其时,月恒集团第四款游戏“天行”正式上线,虚拟世界再起风云!
  • 逆天之绝世天才小姐

    逆天之绝世天才小姐

    21世纪金牌杀手,神偷,鬼医,因一场算计不小心死了。天玥国,四大世家苏家嫡女,南月城无人不知的废柴。当她变成她时会发生怎样的故事呢?
  • 朕的出逃皇后

    朕的出逃皇后

    听说宁府小姐神秘的很。为何呢?难道是因为太丑。小心宁大小姐将青青放出来咬你们哦。听说宁大小姐要出嫁了。这谁家的公子那么倒霉。是咱大月王朝的皇上。青楼相遇,是为抢人。我说,皇后怎不来抢朕抢回去。
  • 铜雀春朝天阙

    铜雀春朝天阙

    她是酒肆里卖唱的小歌女,她是歌舞堂前花蕊初绽的乐伎。初长成时,她遇到了那个翩翩少年,却深陷一场又一场的骗局与谋算。命运,只是权贵重臣掌上的那颗砂砾,她被抛到了一个朝不保夕的世界。看到一场又一场的死亡,眼泪终于不再落下来,她迈开步子,从歌舞画堂前,一步一步,走上了宫阙的最高处。