分解质因式

数学定理：根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。

即：任何一个数都可以写成 $$N = P_{p1}^{a1} + P_{p2}^{a2} + \ldots + p_{pk}^{ak} $$ 其中P为质数

故我们引伸出分解质因数的算法：

原理：我们从第一个质因数开始枚举到\(\sqrt{n}\) 如果其能整除，则说明它是n的一个质数。

但，也许有些人会疑惑它这样子枚举不是会枚举到合数吗？

确实，他会枚举到合数，但是这些合数在我们分解质因数的途中也被分解掉了，故而枚举不到这些合数。

即：设我们分解一个质因数\(N\)则我们会从2开始分解它

​ 我们会尝试它能不能被\(P_1\)分解，则被2分解，如果可以，我们就执行\(N = N / P_1\) 然后执行\(N = N / P_2\) ， \(N = N / P_3\) \(\ldots\) \(N = N / P_k\) 在此途中，我们每枚举到\(P_i\)的时候,设从 \(2 \sim i-1\)此时有一个合数是\(N\)的约数，设其为\(d\)。但我们这个合数也可以被分解为 $$d = P_{p1}^{b1} + P_{p2}^{b2} + \ldots + p_{pi-1}^{bi-1} $$ 故而这个合数自然而然的在前面的枚举的过程中被分解掉了。

​ 所以总结来说，既然\(2\sim i-1\)这个过程中所有合数都被分解之前的质因数除掉了，所以如果我们取到了新的可以整除\(N\)的数\(num\)的话，这个\(num\)只能是新出现的质因数\(P_i\) 了

代码：（yxc版本）

#include <iostream>
#include <algorithm>

using namespace std;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/49974/
来源：AcWing