随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 177787
  • 排名 - 147

最新评论

阅读排行榜

评论排行榜

The Sieve of Eratosthens
爱拉托逊斯筛选法


(原创链接:http://www.wutianqi.com/?p=264[2:23]
思想:对于不超过n的每个非负整数P,删除2*P, 3*P…,当处理

完所有数之后,还没有被删除的就是素数。

若用vis[i]==1表示已被删除,则代码如下:
—————————————————–
代码一:

1memset(vis, 0sizeof(vis));
2for(int i = 2; i <= 100; i++)
3    for(int j = i*2; j <= 100; j += i)
4        vis[j] = 1;


上面的代码效率已经很高了。
但还可以继续优化。
看一个改进的代码:
——————————————————
代码二:

 1int m = sqrt(double(n+0.5));
 2 
 3for(int i = 2; i <= m; i++)
 4    if(!vis[i])
 5    {
 6        prime[c++= i;
 7        for(int j = i*i; j <= n; j += i)
 8        {
 9            vis[j] = 1;
10        }

11    }



——————————————————
先分析代码一:
这个代码就是简单的将Eratosthenes筛选法描述出来。不用多说。
分析代码二:
考虑几点:
1.为何从i=2~m?
因为下面的j是从i*i开始的。
2.为何j从i*i开始?
因为首先在i=2时,偶数都已经被删除了。
其次,“对于不超过n的每个非负整数P”, P可以限定为素数,
为什么?
因为,在 i 执行到P时,P之前所有的数的倍数都已经被删除,若P

没有被删除,则P一定是素数。
而P的倍数中,只需看:
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
(因为P为素数,所以为奇数,而偶数已被删除,不需要考虑p*(p

-1)等)(Tanky Woo的程序人生)
又因为(p-4)*p 已在 (p-4)的p倍中被删去,故只考虑:
p*p, p*(p+2)….即可
这也是i只需要从2到m的原因。
当然,上面 p*p, p*(p+2)…的前提是偶数都已经被删去,而代码

二若改成 j += 2*i ,则没有除去所有偶数,所以要想直接 加2*i

。只需在代码二中memset()后面加:
for(int i = 4; i <= n; i++)
if(i % 2 == 0)
vis[i] = 1;
这样,i只需从3开始,而j每次可以直接加 2*i.
------------------------------------------------------
这里用代码二给大家一个完整的代码:

 1//版本二
 2//Author: Tanky Woo
 3//Blog: www.wutianqi.com
 4 
 5#include <stdio.h>
 6#include <string.h>
 7#include <math.h>
 8int vis[100];
 9int prime[100];
10int c = 0;
11int n;
12int main()
13{
14    scanf("%d"&n);
15    int cnt = 1;
16 
17    memset(vis, 0sizeof(vis));
18    int m = sqrt(double(n+0.5));
19 
20    for(int i = 2; i <= m; i++)
21        if(!vis[i])
22        {
23            prime[c++= i;
24            for(int j = i*i; j <= n; j += i)
25            {
26                vis[j] = 1;
27                //printf("%d\n", j);
28            }

29        }

30 
31    for(int i = 2; i < n; i++)
32    {
33        if(vis[i] == 0)
34        {
35            printf("%d ", i);
36            cnt++;
37            if(cnt % 10 == 0)
38                printf("\n");
39        }

40    }

41    printf("\ncnt = %d\n", cnt);
42    return 0;
43}



完毕。


欢迎大家和我交流。(我的博客:http://www.wutianqi.com/)




posted on 2010-08-04 13:55 Tanky Woo 阅读(1154) 评论(1)  编辑 收藏 引用

FeedBack:
# re: The Sieve of Eratosthens(爱拉托逊斯筛选法)分析  2010-08-04 15:06 schindlerlee
搜 线性筛法  回复  更多评论
  

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