先建質數表，再去分析，若沒辦法除盡(5萬內)，則剩下的必為質數(必須輸出)

因為不是5萬內的質數,那剩餘的必定是質數.

2009/7/20 新增第2程式碼 (線性篩法找質數+內建涵式用變數帶 時間-10ms)
/*************************************************************/

#include<stdio.h>  
#include<stdlib.h>  
#include<math.h>  
int math[5200]={0};  
main()  
{  
 int n,a,b,c,m=1;
 math[0]=2;  
 for(a=3;a<50000;a=a+2)/*5W*5W已經2.5E 無須建更大*/ 
  {  
   int flag=0;  
   for(b=0;math[b]<=sqrt(a);b++)  
    {  
     if(a%math[b]==0)  
      {  
       flag=1;  
       break;  
      }  
    }  
    if(flag==0)  
     {  
      math[m]=a;  
      m++;  
     }  
  }  
 while(scanf("%d",&n)==1&&n!=0)  
  {  
   int flag=0;  
   printf("%d = ",n);  
   if(n==1) {printf("1\n");continue;}  
   if(n==-1) {printf("-1\n");continue;}  
   if(n<0) {n=n*-1;printf("-1");flag=1;}  
   for(a=0;math[a]<=sqrt(n);a++)  
    {  
     while(n%math[a]==0)  
      {  
       if(flag==0)  
        {  
         printf("%d",math[a]);  
         flag=1;  
        }  
       else 
        printf(" x %d",math[a]);  
        n=n/math[a];   
      }  
      if(n==1)  
       break;  
      if(n<math[a])  
       break;   
    }   
    if(n!=1)/*如果沒辦法整除完畢 必為質數*/ 
     {  
      if(flag==0) printf( "%d" ,n) ;  
      else printf( " x %d" ,n) ;  
    }         
    printf("\n");  
  }  
 return 0;  
}

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

#include<stdio.h>  
#include<stdlib.h>  
#include<math.h>  
int math[5200]={0};  
main()  
{  
 int n,a,b,c,m=0;
 char num[100001]={0};
 for(a=2;a<50000;a++)
      if(num[a]==0)
        {
           math[m]=a;
           m++;
           for(b=2;a*b<=50000;b++)
             num[a*b]=1;
        }
 while(scanf("%d",&n)==1&&n!=0)  
  {  
   int flag=0,nn=sqrt(abs(n))+1;  
   printf("%d = ",n);  
   if(n==1) {printf("1\n");continue;}  
   if(n==-1) {printf("-1\n");continue;}  
   if(n<0) {n=n*-1;printf("-1");flag=1;}  
   for(a=0;math[a]<=nn;a++)  
    {  
     while(n%math[a]==0)  
      {  
       if(flag==0)  
        {  
         printf("%d",math[a]);  
         flag=1;  
        }  
       else 
        printf(" x %d",math[a]);  
        n=n/math[a];   
      }  
      if(n==1)  
       break;  
      if(n<math[a])  
       break;   
    }   
    if(n!=1)/*如果沒辦法整除完畢 必為質數*/ 
     {  
      if(flag==0) printf( "%d" ,n) ;  
      else printf( " x %d" ,n) ;  
    }         
    printf("\n");  
  }  
 return 0;  
}