摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

範例輸入:

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;  
}