ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0

转载文章 : 转载自Tanky Woo 的程序人生 , <------- 请大家多多支持奋斗哥哈


The Sieve of Eratosthees
爱拉托逊斯筛选法思想:对于不超过n的每个非负整数P,删除2*P, 3*P…,当处理

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

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

  1. memset(vis, 0, sizeof(vis));
  2. for(int i = 2; i <= 100; i++)
  3. for(int j = i*2; j <= 100; j += i)
  4.   vis[j] = 1;
复制代码
上面的代码效率已经很高了。
但还可以继续优化。
看一个改进的代码:
——————————————————
代码二:
  1. int m = sqrt(double(n+0.5));

  2. for(int i = 2; i <= m; i++)
  3. if(!vis[i])
  4. {
  5.   prime[c++] = i;
  6.   for(int j = i*i; j <= n; j += i)
  7.   {
  8.    vis[j] = 1;
  9.   }
  10. }
复制代码
——————————————————
先分析代码一:
这个代码就是简单的将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)等)
又因为(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 = 1;
这样,i只需从3开始,而j每次可以直接加 2*i.
——————————————————
这里用代码二给大家一个完整的代码:
  1. //版本二
  2. //Author: Tanky Woo
  3. //BBS:www.cppleyuan.com
  4. #include <stdio.h>
  5. #include <string.h>
  6. #include <math.h>
  7. int vis[100];
  8. int prime[100];
  9. int c = 0;
  10. int n;
  11. int main()
  12. {
  13.         scanf("%d", &amp;n);
  14.         int cnt = 1;

  15.         memset(vis, 0, sizeof(vis));
  16.         int m = sqrt(double(n+0.5));

  17.         for(int i = 2; i <= m; i++)
  18.                 if(!vis[i])
  19.                 {
  20.                         prime[c++] = i;
  21.                         for(int j = i*i; j <= n; j += i)
  22.                         {
  23.                                 vis[j] = 1;
  24.                                 //printf("%d\n", j);
  25.                         }
  26.                 }

  27.         for(int i = 2; i < n; i++)
  28.         {
  29.                 if(vis[i] == 0)
  30.                 {
  31.                         printf("%d ", i);
  32.                         cnt++;
  33.                         if(cnt % 10 == 0)
  34.                                 printf("\n");
  35.                 }
  36.         }
  37.         printf("\ncnt = %d\n", cnt);
  38.         return 0;
  39. }
复制代码
完毕。

欢迎大家和我交流。 

转载文章 : 转载自Tanky Woo 的程序人生

Feedback

# re: The Sieve of Eratosthees ( 爱拉托逊斯筛选法 数论 筛法 )  回复  更多评论   

2010-08-07 20:45 by Tanky Woo
Orz奋斗哥

# re: The Sieve of Eratosthees ( 爱拉托逊斯筛选法 数论 筛法 )  回复  更多评论   

2010-08-07 22:41 by MiYu
- -||| 我无语....

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