一、单个数质因数分解

直接上代码：

/**
  * 功能：分解质数因数
  * @param x 待分解的数字
  * @param a 分解后的数组
  * @return 数组的最后一个元素下标
  */
 int Decomposition(int x, int a[]) {
     int cnt = 0;
     for (int i = 2; i <= x / i; i++)
         while (x % i == 0) {
             x /= i;
             a[++cnt] = i;
         }
     if (x > 1)a[++cnt] = x;
     return cnt;
 }

调用方法：

const int N = 110;
 int a[N];

 int cnt = Decomposition(12, a);
 for (int i = 1; i <= cnt; i++)
      cout << a[i] << " ";

适用场景：单个数字的质因数分解。如果是区间内质因数分解，这个办法就太慢了。

二、区间内质因数分解

1、朴素版本

思路：

1、先 get_primes(sqrt(r))取得所有\(r\)的小质数因子（采用欧拉筛，即线筛）。

2、外层循环遍历\([l,r]\)之间的每个数字，内层循环遍历这些质数因子，如果能被整除掉，就一直除干净，再没有这个质数因子。

3、处理完成后有两种可能 ，第一种商是\(1\)，表示被所有小质数因数除干净了；另一种是商不是\(1\)，表示还存在一个大于\(sqrt(x)\)的大质数因数。

附：C++实现质因子分解的理论基础

优点：
因为采用了先穷举根号内质数因数的办法，所以去掉了很多无用的尝试，对比传统暴力的分解质因数方法

2、优化版本

质因数分解专题