题解 P1075 【质因数分解】
这题有更优的解法！
先介绍一下什么叫做质因数：
质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式 。只有一个质因子的正整数为质数。
每个合数都可以写成几个质数（也可称为素数）相乘的形式 ，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。
质因数 就是一个数的约数，并且是质数。
比如8=2×2×2，2就是8的质因数；
12=2×2×3，2和3就是12的质因数。
把一个式子以12=2×2×3的形式表示，叫做分解质因数。
把一个合数写成几个质数相乘的形式表示，这也是分解质因数 ，如16=2×2×2×2，2就是16的质因数。
把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。 分解质因数只针对合数。（分解质因数也称分解素因数）求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。
分解质因数的方法是先用一个合数的最小质因数去除这个合数，得出的数若是一个质数，就写成这个合数相乘形式；若是一个合数就继续按原来的方法，直至最后是一个质数 。
分解质因数的有两种表示方法，除了最常用的“短除分解法”之外，还有一种方法就是“塔形分解法”。
分解质因数对解决一些自然数和乘积的问题有很大的帮助，同时又为求最大公约数和最小公倍数做了重要的铺垫。
Pollard Rho因数分解
1975年，John M. Pollard提出了第二种因数分解的方法，Pollard Rho快速因数分解。该算法时间复杂度为 。
分解质因数代码：
将一个正整数分解质因数。例如：输入90，打印出90=233*5。
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
(2)如果n>k，但n能被k整除，则应打印出k的值，并用n除以k的商作为新的正整数n，重复执行第一步。
(3)如果n不能被k整除，则用k+1作为k的值，重复执行第一步。
然后粘代码：
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
int n;
int i,j;
cin>>n;
for(i=2;i<=n;i++)
{
if(n%i==0)
{
cout<<n/i<<endl;
break;
}
}
return 0;
}