10萬元買進高殖利率個股12檔巴菲特眼中的優質台股超萌!原來狗狗也會裝可愛父只吃白飯還被打? 鄰...
2010-01-06 14:30:24 人氣(3,342) | 回應(1) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

奇摩知識+ 輸出N以內的所有質數

0
收藏
0
推薦

範例輸入:

10

範例輸出:

2 3 5 7

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int Prime[5200]={0},p;
int prime()  //建出50000以內的質數
{
  char num[50000]={0};
  int a,b,m=0;
  for(a=2;a<50000;a++)   //線性篩法
      if(num[a]==0)   //如果它是個質數  則把它的倍數刪光
        {  
           Prime[m++]=a;  
           for(b=2;a*b<=50000;b++)   
             num[a*b]=1;  
        }
   return m;
}
int PrimeJudge (int num)
{
   int a,yes=0,s=(int)sqrt(num);  //在外面做開根號  內建很耗時間
   for(a=0;a<p&&Prime[a]<=s;a++) //質數判斷  跑2~sqrt(N) 切記要含!
      if(num%Prime[a]==0)  //判斷不是則跳出
         {yes=1;break;}
   if(yes==0) //回傳對與不對
      return 1;
   else
      return 0;  
}
main()
{
 p=prime();
 int n,a;
 while(scanf("%d",&n)==1)
     {
        for(a=2;a<=n;a++)
            if(PrimeJudge(a)==1) printf("%d ",a);
        puts("");
     }
 return 0;  
}


 

台長:來源不明
人氣(3,342) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類

獻醜了
您確定這個程式有到「線性」嗎?
你這個程式的prime()在刪除2,3的倍數十,重複刪除了6,12,18...等2,3共同的倍數因此我認為此程式的時間複雜度不是呈現線性的性質!
2010-06-22 18:29:58
我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中的英文字(不分大小寫) (ex:ABCD)

(有*為必填)
詳全文