浙江大学PAT上机题解析之2-07. 素因子分解

给定某个正整数N，求其素因子分解结果，即给出其因式分解表达式 N = p1^k1 * p2^k2 *…*pm ^km。

输入格式说明：

输入long int范围内的正整数N。

输出格式说明：

按给定格式输出N的素因式分解表达式，即 N = p1^k1 * p2^k2 *…*pm ^km，其中pi为素因子并要求由小到大输出，指数ki为pi的个数；当ki==1即因子pi只有一个时不输出ki。

样例输入与输出：

1024

1024=2^10

1323

1323=3^3*7^2

97532468

97532468=2^2*11*17*101*1291

1

1=1

3

3=3

//关于素因子分解，这是数论中(密码学运用)最基本也是最重要的问题之一，由于本题的数据并不是很大，故可运用下面的简单的方法，但是效率却不是很高(PAT上足以AC),若有兴趣可参见TAOCP (<<计算机程序设计与艺术>>,计算机界"易筋经"级别书籍)卷二中的半数值算法中有关的数学推导与证明。

#include <iostream>#include <cmath>using namespace std;int main(){   long int N;   long int i;   long int m;   int k=0;   bool flag = false;   bool isPrime = true;   cin>>N;  m  =  (long int)sqrt(N+0.5);   cout<<N<<"=";  for (i=2;i<=m;i++)  {  k=0;  while(N%i==0)  {   k++;  N/=i;  isPrime = false;  }      if (k)  {  if (flag)  cout<<"*";  else  flag = true;  if (k==1)  cout<<i;  else  cout<<i<<"^"<<k;    }  }  if (isPrime)  cout<<N;  cout<<endl;//system("pause");return 0;}