原创
给定某个正整数 N，求其素因子分解结果，即给出其因式分解表达式 N=p1k1⋅p2k2⋯pmkm。
输入格式：
输入long int范围内的正整数 N。
输出格式：
按给定格式输出N的素因式分解表达式，即 N=p1k1*p2k2…pm^km，其中pi为素因子并要求由小到大输出，指数ki为pi的个数；当ki为1即因子pi只有一个时不输出ki。
输入样例：
1323
输出样例：
1323=33*72
猛地一看像是（深搜+剪枝 处理因式分解）。仔细一想并不是。
首先，我看到题的时候第一反应是这个输出有问题，如果按照输出要求，素因子分解不唯一怎么办？
你看，还是知识点有盲区吧，数学基础踏实了，根本不会有这种问题。数学上有正整数的唯一分解定理，即：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。
这个定理是用反证法证明的。
假设存在某些数，它们有至少两种分解方法。那么根据上文提到的“非空正整数集里存在最小的元素”，一定有一个最小的数M，它能用至少两种方法表示成质数的乘积：
M = P1 * P2 * … * Pr = Q1 * Q2 * … * Qs
下面我们将看到，这种假设会推出一个多么荒谬的结果来。不妨设P1 <= P2 <= … <= Pr, Q1 <= Q2 <= … <= Qs。显然，P1是不等于Q1的，不然两边同时约掉它，我们就得到一个更小的有两种分解方法的数。不妨设P1 < Q1，那么我们用P1替换掉等式最右边中的Q1，得到一个比M更小的数T = P1 * Q2 * Q3 * … * Qs。令M’ = M – T，我们得到M’的两种表达：
M’ = (P1 * P2 * … * Pr) – (P1 * Q2 * … * Qs) = P1 * (P2 * .. * Pr – Q2 * … * Qs) …… (1)
M’ = (Q1 * Q2 * … * Qs) – (P1 * Q2 * … * Qs) = (Q1 – P1) * Q2 * … * Qs ……………… (2)
由于T比M小，因此M’是正整数。从(1)式中我们立即看到，P1是M’的一个质因子。注意到M’比M小，因此它的质因数分解方式应该是唯一的，可知P1也应该出现在表达式(2)中。既然P1比所有的Q都要小，因此它不可能恰好是(2)式中的某个Q，于是只可能被包含在因子(Q1-P1)里。但这就意味着，(Q1-P1)/P1除得尽，也就是说Q1/P1-1是一个整数，这样Q1/P1也必须得是整数。我们立即看出，P1必须也是Q1的一个因子，这与Q1是质数矛盾了。这说明，我们最初的假设是错误的。
反正就是求出一个等式来保证了程序的完备性。
在解决这个问题之前请思考：输出格式。因为是它肯定给出了算法要求。
按给定格式输出N的素因式分解表达式，即 N=p1k1*p2k2…pm^km，其中pi为素因子并要求由小到大输出，指数ki为pi的个数；当ki为1即因子pi只有一个时不输出ki。
输出格式首先是个等式并且肯定有等式满足。
其实吧，这就是个数学问题，数学好的这个题水到渠成。
1，等式怎样满足，请思考。
2，如何尽可能少的在long int范围内判断素数，请思考。
3，表达式底数从小到大排序，如何实现，请思考。
4，指数如何实现，请思考。
对于第一个问题。
满足等式可以用整除（即余数为0）判断解决。
对于第二个问题，很有必要在第一问整除除数必须要是素数。所以用数组记录数是否是素数是需要的，故埃氏筛选法首选。
对于第三个问题
for循环，用vector记录，数组也行。
对于第四个问题，到这儿你会发现，第四个问题好难解决。不要慌，你能发现可以利用第三问，如果可以整除就把数记录，那么如果记录的数如果一样那么指数++；遍历也往后推移。
OK，上代码
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
vector<int>P;
int A[10000]={0};
int i,j;
for(i=2;i<10000;i++)
{
if(A[i])
{
for(j=i*i;j<10000;j+=i)
{
A[j]=1;
}
}
}//艾氏筛选法筛选素数
long n;
cin>>n;
cout<<n<<"=";
while(1)
{
long t=n;
for(int k=2;k<=sqrt(n);k++)
{
if(A[k]==0&&n%k==0)
{
P.push_back(k);
n/=k;
break;
}
}
//记录可整除素数数组
if(n==t)
{
P.push_back(n);
break;
}
}
//当然特例，该数本身就是素数，能整除的只有其本身。
int sum=1;
for(int q=0;q<P.size()-1;q++)
{
if(P[q]==P[q+1])
{
sum++;
}
//如果出现指数形式，不输出q往后移。同时记录指数，如果不相等，就可以把状态输出。
else{
if(sum==1)
cout<<P[q]<<"*";
//一个的时候不用出现“^”符号。
else{
cout<<P[q]<<"^"<<sum<<"*";
sum=1;
//不止一个的时候输出"^",并且输出后状态初始。
}
}
}
//sum为指数
//最后一个后面没有符号，当然得特殊处理。
if(sum==1)
cout<<P[P.size()-1];
else
cout<<P[P.size()-1]<<"^"<<sum;
return 0;
}
over，只要数学好，啥题都能做。
