2009-10-02 22:22:25來源不明

很大的質數判斷

作法: 建出質數表,在做搜尋

/**********************************************************/

#include<stdio.h>     
#include<stdlib.h>     
#include<math.h>     
int Prime[5200]={0},p;       
char pp[50001]={0};     
int N,M,S;     
int prime()        
{        
 int a,b,m=1;     
 Prime[0]=2;        
 for(a=3;a<=50000;a=a+2)           
      if(pp[a]==0)           
        {           
           Prime[m]=a;           
           m++;           
           for(b=3;a*b<=50000;b=b+2)           
             pp[a*b]=1;           
        }        
   return m;        
}      
int Divisors (int num)     
{     
   int a,b,sq=(int)sqrt(num),find=0;     
   for(a=0;Prime[a]<=sq;a++)     
        if(num%Prime[a]==0)     
          {     
            find=1;break;      
          }     
   if(find==1) { putchar('n');putchar('o');putchar('\n'); }
   else { putchar('y');putchar('e');putchar('s');putchar('\n'); }
}     
    
main()     
{     
 p=prime();      
 int a,b;     
 while(scanf("%d",&N)==1)              
     Divisors(N);             
 return 0;        

上一篇:海星

下一篇:2.字串處理