奇摩知識+ 輸出N以內的所有質數
範例輸入:
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;
}
您確定這個程式有到「線性」嗎?
你這個程式的prime()在刪除2,3的倍數十,重複刪除了6,12,18...等2,3共同的倍數因此我認為此程式的時間複雜度不是呈現線性的性質!