$\Huge\color{orchid}{点击此处获取更多干货}$

质因数分解和算术基本定理

因数是约数的另一个名称，一个数的因数中，是质数的那些就叫做该数的质因数。这个概念一般对于合数来说意义更大（质数只有1和自身两个因数，没太大必要分解）
对于一个合数来说，一个简单粗暴的分解质因数$\text{(Prime Factorization)}$方法，就是在所有因数中升序找出质数，然后把它们除尽。找质因数这件事，就要牵扯到算术基本定理了，其表达式如下：
$$N=\prod_{i=1}^{n}(p_i^{a_i}) =p_1^{a_1}*p_2^{a_2}*…*p_n^{a_n}$$
其中$p_i$是比$N$小的质数，$a_i$是其对应的幂。用自然语言描述就是，任何合数都可以表示为若干质数幂的乘积，这些质数全都比该数小。由此，可以继续得出以下4条推论：
1. 合数$N$某因数$f$的质因数，同样也是$N$的质因数
2. 对于推论1中的$f$，如果它是合数，那么$f$同样可以表示为若干$N$的质因数幂的乘积，且这些质因数全都小于$f$（理由就是推论1，$f$的质因数全都是$N$的质因数，且合数的质因数不可能包含自身）
3. 一个合数的因数，去掉1和自身，按照升序排列时，一定存在某最大的正整数$L$，使得因数序列长度为$L$的前缀中，每一个数都是质数（由上述两条推论得出，另一种说法就是该序列中合数一定不会出现在序列头端）
4. 在$N$的所有质因数中，如果存在大于$\sqrt{N}$的质因数$p$，那么该项在算术基本定理的表达式中，对应的指数必然是1（由$y=\sqrt{x}$在正整数集合上的单调增加性质得出，$p$的指数不小于2时，必然会比$N$大）

下面是对上述几个推论的一些说明：

以及对于算法实现，最重要的一条事实：如果按照升序枚举每个因数并将其除尽，能被选中的只有质因数。比如上面的156($2^2*3^1*13^1$)，除尽2和3之后，留下的应该是$2^0*3^0*13^1$，如果要继续选择4去除尽，和在剩下的部分中再除尽两个2是一回事，显然这是不可能的，对于6，12同理，只有最后剩下的质数13能被选中并除尽

C++ 代码

/**
* @brief 分解质因数
* @param 待分解的数
* 不仅要得出质因数有哪些，还要得出它们对应的指数
*/
void primeFactorization(int x) {
    for (int i = 2; i <= x / i; i++) {      //跟质数判断一样试除每个整数
        int pw = 0;
        while(x % i == 0) {                 //将该数除尽，有几次方就除几个
            x /= i;
            pw++;
        }
        if (pw > 0) {                       //只有当指数大于0时才有意义
            cout << i << " " << pw << endl;
        }
    }
    if (x > 1) {                            //如果还剩下，那么就代表这是那个大于sqrt(x)的
        cout << x << " 1" << endl;
    }
}