问题描述
- 任何一个合数都可以写成几个质数相乘的形式，这几个质数叫做这个合数的质因数。编程实现分解质因数。
测试样例
| 输入 |
输出 |
| 12 |
2 2 3 |
| 16 |
2 2 2 2 |
方法一：枚举
方法二：Pollard Rho因数分解
- 1975年，John M. Pollard提出了第二种因数分解的方法，Pollard Rho快速因数分解。该算法时间复杂度为O（n^(1/4)）。
- 原理（以二重循环为例）从最小质数i=2开始循环到n，（1）当i可以整除n时，i为因数，执行n=n/i，（2）继续除i。当i不能被整除时，执行i++。继续执行（1）直到i=n
- 二重循环
//n为待分解的合数
for(i=2;i<=n;i++)
while(n!=i) {
if(n%i==0){
cout<<i<<' ';
n=n/i;
}
else
break;
}
cout<<n;
//调用方法recursion(m,2)
void recursion(int m, int n){
if (m >= n) {
while (m%n) n++;
m/=n;
recursion(m, n);
cout << n << endl;
}
}
参考文章
