SSOJ2662正整数的唯一分解定理
3057+
作者：crxis 发布：2018-05-18 分类：数论
题目大意：将一个大于1的自然数进行质因数分解，以“n=质因子乘积”的形式输出来。
题目描述
算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。
先给出一个大于1的自然数，请将其写成质因数乘积的形式，如：
6=2*3
12=2*2*3
25=5*5
37=37
……
输入
输入一个大于1的自然数
输出
输出质因数分解等式
样例输入
12345
样例输出
12345=3*5*823
解题思路
对于大于1的自然数n，其质因子从小打到可能是2、3、5、7……
我们可以从小到大枚举因子，发现一个因子i，就除以i，除到不能整除i为止，这样n就少了一种因子了。
如果这个因子是2，那么n除以多次2之后，后面就不会在找到4这种合数因子了。
因此，后面继续这样找因子，找到的都是质因子，不可能是合数因子：如果有合数因子，合数可以质因数分解，说明存在更小的因子，与从小到大枚举因子相矛盾。
最后需要注意的是，一个数的因子，一半小于等于√n，另外一半大于等于√n，为避免超时，我们只需要枚举前面小的一半；这样的话，可能会漏掉一个大的质因子，如21=3*7，i只会枚举到√21=4，7就不会枚举了；因此，如果最后n还大于1，那么剩下的n不能再分解必是一个较大的质因子。
时间复杂度是O(√n)，虽然是嵌套循环，但内重循环只会让外重循环更快介绍，循环次数并不是乘积的关系。
程序实现
