埃拉托斯特尼发明的”素数筛子“ - 基础数学 我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

我爱数学网-数学爱好者的家园-中国专业化的数学论坛之一

查看: 1016|回复: 8

[数论] 埃拉托斯特尼发明的”素数筛子“

[复制链接]

120

主题

331

帖子

2037

积分

初中二年级

Rank: 4Rank: 4

积分
2037

最佳新人活跃会员

发表于 2014-10-16 11:03:08 | 显示全部楼层 |阅读模式
埃拉托斯特尼发明的”素数筛子“
        埃氏筛,是埃拉托斯特尼筛法的简称,是由埃及数学家埃拉托斯特尼所提出的一种简单检定素数的一种方法。
大概思路如下:
自然数可分成1、素数、合数这三类,一定范围内的自然数中,哪些数是素数呢?古时候,希腊有位叫做埃拉多染尼的数学家想出了如下办法:当时,他将1000内的自然数依次写在一块硬方格板上,然后用2试除各数,将能被整除的都用刀子剜掉;继2之后再用3来如此而行;3之后再用5来如此而行……这样一直进行到无法进行而为止,最后再剜掉1。于是,剩下的没能被剜掉的数便是1000内的素数。  
由于得到的是张像筛子一样的图,所以,人们便将这种方法叫做埃拉多染尼筛法。


具体例子如下:
第一步,列出如下这样以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


第二步,标出序列中的第一个素数,主序列变成:
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25


第三步,将剩下序列中,第二项开始每隔一项划掉(2的倍数,用红色标出。),主序列变成:
3 5 7 9 11 13 15 17 19 21 23 25


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


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


剩下的序列中第一个素数是3,将主序列中3的倍数划出(红色),主序列变成:
5 7 11 13 17 19 23 25
我们得到的素数有:2,3。
25仍然大于3的平方,所以我们还要返回第二步:
现在序列中第一个素数是5,同样将序列中5的倍数划出,主序列成了:
7 11 13 17 19 23
我们得到的素数有:2 3 5 。
因为25等于5的平方,跳出循环.
结论:去掉红色的数字,2到25之间的素数是:2 3 5 7 11 13 17 19 23。
もっと もっと つよくなりてぇ
回复

使用道具 举报

10

主题

303

帖子

1376

积分

小学六年级

Rank: 3

积分
1376

活跃会员

发表于 2014-10-16 16:33:56 | 显示全部楼层

回帖奖励 +1

我是来抢沙发的
唯一看透真相的是一个外表看似个小孩,智慧却过于常人的名侦周薇妮
回复

使用道具 举报

0

主题

2

帖子

67

积分

幼儿园

Rank: 1

积分
67
发表于 2014-10-17 12:27:40 | 显示全部楼层
很不错
回复

使用道具 举报

0

主题

1

帖子

91

积分

幼儿园

Rank: 1

积分
91
发表于 2014-10-17 12:33:57 | 显示全部楼层
好帖就是要顶
回复

使用道具 举报

0

主题

2

帖子

57

积分

幼儿园

Rank: 1

积分
57
发表于 2014-10-17 12:40:26 | 显示全部楼层
真心顶
回复

使用道具 举报

0

主题

1

帖子

56

积分

幼儿园

Rank: 1

积分
56
发表于 2014-10-17 12:45:32 | 显示全部楼层
说的非常好
回复

使用道具 举报

0

主题

1

帖子

59

积分

幼儿园

Rank: 1

积分
59
发表于 2014-10-17 12:23:44 | 显示全部楼层
不错不错
回复

使用道具 举报

0

主题

21

帖子

132

积分

小学一年级

Rank: 2Rank: 2

积分
132
发表于 2014-10-18 09:24:55 | 显示全部楼层
回复

使用道具 举报

50

主题

1955

帖子

3568

积分

高中二年级

Rank: 5Rank: 5Rank: 5

积分
3568

活跃会员灌水之王最佳新人

发表于 2015-3-8 20:23:06 | 显示全部楼层
长知识了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 会员注册

本版积分规则

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc

关于我们 | 网站地图 | 我爱数学网 ( 沪ICP备16005585号-3  

GMT+8, 2020-5-28 23:40 征信网

快速回复 返回顶部 返回列表