浙大1390 素数问题

浙大1390 素数问题

1390素数问题
Time Limit:1000MS  Memory Limit:32768K

Description:
任何一个整数，都可以有多个素数相乘，现在给你一个数N(1< N<=65535)，请你把它分成多个素数相乘。

Input:
输入一个整数N，输入0表示结束.
Output:
输出相应的结果.
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时就退出循环了，于是程序将4也当作了素数
  {
    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;//跳到无限循环的唯一地方
    }
   if(x%tag==0)
    {
     if(flag>0) cout<<'*';         
     cout<<tag;
     x/=tag;
     flag++;
    }
   else
   {   tag++;//没有这一句，输入65535进入死循环
 
       while(!prime(tag))
       tag++;
   }         
 }

} 
     

int main()
{int t;
while(cin>>t)
{
 if(!t) break;
 f(t);
             
            
}
  system("pause");
   return 0;
}
//用VC出现编译错误，用GCC提交成功,
//因为sqrt函数给的参数要转化为浮点数

 

解答二：

#include <iostream>
#include <cmath>
using namespace std;
bool prime(int x)
{
 if(x==2) return true;
 int q=sqrt( (double)x );//注意这里的转化
 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)//变化后的数要重新拿去用if语句做判断就需要一个循环
    {
  if(prime(x))
  {
   if(ans>0) cout<<'*';
   cout<<x<<endl;
   return ;
  }
  if(x%tag==0)//不是素数跳到这里，先除以最小的素数2
        //如果既不是素数，也不是被2整除，再跳到else部分，让除数自增到一个较大的素数
  {
   if(ans>0) cout<<'*';
   cout<<tag;
   x/=tag;
   ++ans;//用来控制什么时候输出*这个符号
  }
  else
  {
   ++tag;
   while(!prime(tag))//当除数不是素数时将其自加直到为素数为止
    ++tag;
  }
 }
}
int main()
{
 int n,tag=0,i;
 while(cin>>n)
 {
  if(!n) break;
  f(n);
 }
 return 0;
}