标题:筛法求质数
只看楼主
wangcheng911
Rank: 2
等 级:论坛游民
帖 子:59
专家分:45
注 册:2009-9-23
结帖率:77.78%
已结贴  问题点数:10 回复次数:7 
筛法求质数
求2-100间的所有质数。
。把所用的依次摆开,再依次筛掉2,3,5,7。。。。。。到47的倍数。不能用乘除只能用加减以加快速度。谁会啊?我想的头都疼了
搜索更多相关主题的帖子: 质数 筛法 
2009-10-25 01:15
UserYuH
Rank: 12Rank: 12Rank: 12
来 自:毅华
等 级:火箭侠
威 望:8
帖 子:720
专家分:3300
注 册:2009-8-10
得分:10 
筛法,只有加。
程序代码:
#include <stdio.h> 
int main(void) 
{ 
 int a[101],i,j; 
 for(i=2;i<=100;i++) 
   a[i]=i; 
 
 for(i=2;i<=50;i++) 
   { 
    if(a[i]!=0) 
      for(j=i+i;j<=100;j+=i) 
        a[j]=0; 
   } 
 
 for(i=2;i<=100;i++) 
   if(a[i]!=0)printf("%3d",a[i]); 
 printf("\n\n"); 
 return 0; 
}

努力—前进—变老—退休—入土
2009-10-25 03:13
wangcheng911
Rank: 2
等 级:论坛游民
帖 子:59
专家分:45
注 册:2009-9-23
得分:0 
大哥  多谢啊!
高手就是不一样啊!
2009-10-29 23:04
wangcheng911
Rank: 2
等 级:论坛游民
帖 子:59
专家分:45
注 册:2009-9-23
得分:0 
可是为什么要用“if(a[i]!=0)  ”这一句呢?
我试了试没有也可以的,
就是不明白这句的作用,不知道为什么会有这一句。
大哥帮忙解释一下啊,麻烦了、、、、、、
2009-10-29 23:16
UserYuH
Rank: 12Rank: 12Rank: 12
来 自:毅华
等 级:火箭侠
威 望:8
帖 子:720
专家分:3300
注 册:2009-8-10
得分:0 
筛选法嘛,如开始2的倍数都筛选掉了,到4时已经是筛掉的数,就不用再筛选一次4的倍数,即无用又耗时,a[i]!=0 就是判断是否是已经被筛掉的。

[ 本帖最后由 UserYuH 于 2009-10-30 00:23 编辑 ]

努力—前进—变老—退休—入土
2009-10-29 23:34
dreamsea
Rank: 2
等 级:论坛游民
帖 子:25
专家分:24
注 册:2009-10-25
得分:0 
看不太懂
2009-10-30 19:02
fanfeng
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2009-8-28
得分:0 
回复 楼主 wangcheng911
厉害!佩服!
2009-10-30 19:52
wangcheng911
Rank: 2
等 级:论坛游民
帖 子:59
专家分:45
注 册:2009-9-23
得分:0 
就是不一样啊。我怎么就没想到呢!
2009-11-01 01:16



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-289828-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.023912 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved