登陆注册
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。

同类推荐
  • 梦起梦落枫心飘荡

    梦起梦落枫心飘荡

    亲爱的朋友们,你是否看倦了偶像剧中的甜蜜美满,你是否心中仍深刻记着那部复仇剧,你是否喜欢带来欢乐的喜剧,你是否脑中仍能浮现出动作片的速度与激情??????你将见到这样一个小姑娘,她便生活,便思考,思考这个世界是什么样的,周围的人心如何。爱情、亲情、友情.......她会如何面对,她的未来如何?
  • 赵作的爱情

    赵作的爱情

    根据本人的《我的初恋二恋三四五六七八恋》剧本改编的一部小说。
  • 围围裙的拿笔女人1

    围围裙的拿笔女人1

    28岁农村女孩,在经历生活磨难之后,努力成长蜕变的故事!
  • 我和离婚人妻

    我和离婚人妻

    在冷清的某个夜晚我邂逅了穿着情趣被赶出家门的柳如月,忐忑收留,竟无故落入隔壁男人设计自己老婆的圈套里……
  • 姐妹逆袭路

    姐妹逆袭路

    姐们逃离魔屋,开始了新生活。为自己的理想而付出努力。
热门推荐
  • 还我走向你好不好

    还我走向你好不好

    高中就订婚的情侣可不太多啊,只是偏偏这一对明明不相爱却硬要被凑活在一起,好不容易两个人日久生情,却因为一场天大的误会分道扬镳,多年后再一次见面,一个是大总裁,一个是小秘书。当初你从我身边逃走是不是就没有想过我们还会再重逢?我不认识你啊!是么?待会你就认识了,而且是很彻底的认识!
  • 天行

    天行

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

    再生娱乐圈:天坛歌后

    曾经的超模,再次重生,一步一步走向娱乐圈,费尽艰苦,成为天坛歌后......-------------------------“BOSS,夏小姐和千殇集团总裁去了宾馆.....“”千殇集团算个屁,立刻收购了。“”BOSS,夏小姐说,说要带着小少爷跳楼......“”说啥?“”带小少爷跳楼...“某大少爷坐不住了,飙车回家【楼顶】”夏筱依我劝你自己下了,别让我上去抓你。“”.....“【本文绝对宠文,男女主身心干净,位位新坑,欢迎跳坑!”【欢迎关注位位的微博“wei位玖柒”】
  • 谁不想当一个欢乐的中二少女

    谁不想当一个欢乐的中二少女

    本书又名《谁还不想当一个无忧无虑的中二病少女呢?》诺薇儿·亚娜中二少女,本名:王翠花,一个重度妄想症患者,一直以为自己是中世纪的贵族小姐。直到有一天她和一堆脑子里有着各种毛病的一群人被困在了一座荒岛里。一切的原因都是因为什么呢?动起你们聪明的小脑瓜吧,中二的孩子们!
  • 说话的艺术

    说话的艺术

    本书以说话对象的心理、说话的基本技巧、说话的艺术体现三部分,介绍了“说什么”和“怎么说”这两个概念,诠释了“说话也是生活的艺术”这句话,并告诉读者“在人生的胜局中,不会说话是万万不能的”。
  • 一个人的小确幸

    一个人的小确幸

    要么我惊鸿一瞥,浸染你的心间,要么我温柔岁月,遗憾我的时光
  • 吾乱三国

    吾乱三国

    感无常,遥望诸天辰星,叹造化,脚踏寰宇罡斗,执牛耳,肩负历史闸门,我要让那五胡来朝,直呼天朝国威!我要让那蛮夷归服,徒喊不附中华!我要让那诸神膜拜,高唤大道归宗!感谢阅文书评团提供书评支持!
  • 佛陀天

    佛陀天

    背上负一届天山水图,图上重峦叠嶂水天一色,悬剑立中,剑气可纵横万里,剑光可寒荡九洲。佛陀天坐下:祖莲尊者、陆压尊者、三帝、六神、九仙、千灵、万圣、亿将……平凡的故事从这里开始……
  • 问道之踏歌行

    问道之踏歌行

    这个世界,道纹是修仙练气的基础。然而夜无眠却被自己最信任的人所害,道纹被夺。大难不死的他,于他人的身体里重生,却因为没有道纹而无法修仙练气。于是,他选择了一条几乎没人走的路,以书入道,与古人为友,悟圣贤写在书中的意境为己用。当遇到曾经喜欢的人,不能表明身份的他和她之间又摩擦出怎样的火花?本书即写仙侠,也写言情。作者认为,有恩怨情仇的仙侠才是完美的!剧情进展可能比较慢,但绝对值得期待!
  • 天行

    天行

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