埃拉托斯特尼筛法的原理及算法

原理
 1/*算法描述
 2详细列出算法如下：
 3
 4    列出2以后的所有序列：
 5        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 6    标出序列中的第一个素数，也就是2，序列变成：
 7        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 8    将剩下序列中，划摽2的倍数（用红色标出），序列变成：
 9        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
10    如果现在这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。
11
12    本例中，因为25大于2的平方，我们返回第二步：
13    剩下的序列中第一个素数是3，将主序列中3的倍数划出（红色），主序列变成：
14        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
15
16    我们得到的素数有：2，3
17    25仍然大于3的平方，所以我们还要返回第二步：
18    现在序列中第一个素数是5，同样将序列中5的倍数划出，主序列成了：
19        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
20    我们得到的素数有：2 3 5 。
21    因为25等于5的平方，跳出循环.
22
23结论：去掉红色的数字，2到25之间的素数是：2 3 5 7 11 13 17 19 23。
24*/
25/*本描述来自维基百科
26http://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95
27*/
28//算法（随后补上）
posted on 2012-03-22 17:47 血族使天 阅读(556) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理