问题描述

• 任何一个合数都可以写成几个质数相乘的形式，这几个质数叫做这个合数的质因数。编程实现分解质因数。

测试样例

输入	输出
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;
     }
 }

参考文章

• 分解质因数