什么是分解质因数？

将一个数分解成因数，并且保证每个因数是质数！

时间复杂度是O(n)的分解：

朴素分解质因子代码

朴素代码如下：

#include <iostream>

using namespace std;

void divide(int n)
{
    for (int i = 2; i <= n; i ++ )
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0)
            {
                n /= i;
                s ++ ;
            }
            printf("%d %d\n", i, s);
        }
    puts("");
}

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

    return 0;
}

这个代码过不了，TLE，方便理解。

优化分解过程

一个数n中只包含一个大于$\sqrt{n}$ 的质因子

证明：n的因数总是成对出现的，如果d是n的因子，则$\frac{n}{d}$也一定是n的因子。(如2是8的因子，则4也一定是n的因子，8 = 2 * 4)

因为$\sqrt{n}^2 = n$，所以以$\sqrt{n}$为分界线，n的两个质因子一定分布在$\sqrt{n}$的两侧！

所以这样就可以进行优化：

对代码：if (n > 1) printf("%d %d\n", n, 1);的解释

• 如果n正好是i的倍数，如n=8，则n可以被分解成$2^3$，则质因子底数就是2，指数就是3。
• 如果不是倍数，并且n可以刚好被分解成两个质因子相乘，则i是较小的那个质因子底数，n被更新后是与$i^s$相匹配的较大的那个质因子！比如：当n = 30时，n可以被分解成3个质因子相乘$2×3×5$，当i循环到2时，n被更新成15，此时输出i=2，s=1，而15刚好可以被分解成$3*5$，此时n被更新成5后便不能再被分解，则此时i是较小的那个质因子，n是较大的那个质因子！

与试除法判断质数对比

1. 试除法判断质数的算法时间复杂度必定是O($\sqrt{n}$)
2. 分解质因子算法，当$n = 2^N$时，进入循环会被i=2除到最后，n=1，跳出循环的时间复杂度时O($\log{n}$)。最坏的时间复杂度时O($\sqrt{n}$)，平均时间复杂度比试除法判断质数快！

对热度第一题解，评论区n=96时的个人理解

96进入for循环就被2模5次，结果n被更新成3，此时n=3与$2^5$相匹配。

根据代码的结果$底数\ i=2,指数\ s=5$，n是与i相匹配的较大的质因子。因为最后得出的n=3是由6/2得来的。

优化分解质因子代码

#include <iostream>

using namespace std;

void divide(int n)
{
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0)
            {
                n /= i;
                s ++ ;
            }
            printf("%d %d\n", i, s);
        }

    if (n > 1) printf("%d %d\n", n, 1); // n的指数为什么是1呢？因为它是已经和i匹配了，较大的那个质因子只存在一个，上面已经证明!
    puts("");
}

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

    return 0;
}