1390素?cái)?shù)問題
Time Limit:1000MS  Memory Limit:32768K

Description:
任何一個(gè)整數(shù)，都可以有多個(gè)素?cái)?shù)相乘，現(xiàn)在給你一個(gè)數(shù)N(1< N<=65535)，請(qǐng)你把它分成多個(gè)素?cái)?shù)相乘。

Input:
輸入一個(gè)整數(shù)N，輸入0表示結(jié)束.
Output:
輸出相應(yīng)的結(jié)果.
Sample Input:
2
12
16
65535
0
Sample Output:
2
2*2*3
2*2*2*2
3*5*17*257

解答：
#include <iostream>
#include <cmath>
using namespace std;
bool prime(int x)
{
  if(x==2) return true;
  for(int i=2;i<=sqrt((float) x);i++)
  //如果為i<t,輸入16輸出為2*2*4
  //因?yàn)椋瑂qrt(4)等于2時(shí)就退出循環(huán)了，于是程序?qū)?也當(dāng)作了素?cái)?shù)
  {
    if(x%i==0)
    return false;
        
  }
   return true;
} 
void f(int x)
{ int tag=2,flag=0;
  for(;;)
 {
   if(prime(x))
    {
    if(flag>0) cout<<'*';
    cout<<x<<endl;
    return;//跳到無限循環(huán)的唯一地方
    }
   if(x%tag==0)
    {
     if(flag>0) cout<<'*';         
     cout<<tag;
     x/=tag;
     flag++;
    }
   else
   {   tag++;//沒有這一句，輸入65535進(jìn)入死循環(huán)
 
       while(!prime(tag))
       tag++;
   }         
 }

} 
     

int main()
{int t;
while(cin>>t)
{
 if(!t) break;
 f(t);
             
            
}
  system("pause");
   return 0;
}
//用VC出現(xiàn)編譯錯(cuò)誤，用GCC提交成功,
//因?yàn)閟qrt函數(shù)給的參數(shù)要轉(zhuǎn)化為浮點(diǎn)數(shù)

解答二：

#include <iostream>
#include <cmath>
using namespace std;
bool prime(int x)
{
 if(x==2) return true;
 int q=sqrt( (double)x );//注意這里的轉(zhuǎn)化
 for(int i=2;i<=q;++i)
  if(x%i==0) return false;
  return true;
}
void f(int x)
{
 int ans=0;
 int tag=2;
 while(1)//變化后的數(shù)要重新拿去用if語(yǔ)句做判斷就需要一個(gè)循環(huán)
    {
  if(prime(x))
  {
   if(ans>0) cout<<'*';
   cout<<x<<endl;
   return ;
  }
  if(x%tag==0)//不是素?cái)?shù)跳到這里，先除以最小的素?cái)?shù)2
        //如果既不是素?cái)?shù)，也不是被2整除，再跳到else部分，讓除數(shù)自增到一個(gè)較大的素?cái)?shù)
  {
   if(ans>0) cout<<'*';
   cout<<tag;
   x/=tag;
   ++ans;//用來控制什么時(shí)候輸出*這個(gè)符號(hào)
  }
  else
  {
   ++tag;
   while(!prime(tag))//當(dāng)除數(shù)不是素?cái)?shù)時(shí)將其自加直到為素?cái)?shù)為止
    ++tag;
  }
 }
}
int main()
{
 int n,tag=0,i;
 while(cin>>n)
 {
  if(!n) break;
  f(n);
 }
 return 0;
}