思路与算法

先输出原数和等号。按d从2递增试除当前余数，只要能整除就输出一次d并除掉它，直到不能再整除。d*d大于余数时停止，若余数大于1则输出该余数。因子间打印星号，不合并幂次。

正确性说明

处理d前比d更小的质因子已完全除尽。若d能整除余数，d不可能是合数，否则其更小质因子也会整除余数，矛盾，所以输出d为质数。每次除法保持原数等于已输出因子之积乘余数。停止后余数若大于1则必为质数，否则仍有不超过其平方根的因子应继续处理。递增试除并重复输出得到排序后的完整乘积。

复杂度

最多试除O(sqrt(N))个候选，成功除法共O(log N)次，总时间O(sqrt(N)+log N)，额外空间O(1)，初始化O(1)。N为2至20000。

易错点

明确范围包含质数，质数应输出N=N。保存原数后才修改余数。重复因子完整输出，不能合并成指数。最后大质因子不能漏掉。等号和星号周围不额外加空格。

参考代码（C++11）

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    cout << n << '=';
    bool first = true;
    for (int d = 2; d * d <= n; ++d)
        while (n % d == 0) {
            if (!first)
                cout << '*';
            cout << d;
            first = false;
            n /= d;
        }
    if (n > 1) {
        if (!first)
            cout << '*';
        cout << n;
    }
    cout << '\n';
}