1390素數(shù)問題
Time Limit:1000MS  Memory Limit:32768K

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

Input:
輸入一個整數(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
  //因為，sqrt(4)等于2時就退出循環(huán)了，于是程序?qū)?也當作了素數(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進入死循環(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)編譯錯誤，用GCC提交成功,
//因為sqrt函數(shù)給的參數(shù)要轉(zhuǎ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語句做判斷就需要一個循環(huán)
    {
  if(prime(x))
  {
   if(ans>0) cout<<'*';
   cout<<x<<endl;
   return ;
  }
  if(x%tag==0)//不是素數(shù)跳到這里，先除以最小的素數(shù)2
        //如果既不是素數(shù)，也不是被2整除，再跳到else部分，讓除數(shù)自增到一個較大的素數(shù)
  {
   if(ans>0) cout<<'*';
   cout<<tag;
   x/=tag;
   ++ans;//用來控制什么時候輸出*這個符號
  }
  else
  {
   ++tag;
   while(!prime(tag))//當除數(shù)不是素數(shù)時將其自加直到為素數(shù)為止
    ++tag;
  }
 }
}
int main()
{
 int n,tag=0,i;
 while(cin>>n)
 {
  if(!n) break;
  f(n);
 }
 return 0;
}