正经题解｜因子分解

【算法分析】

在 $dfs(x)$ 函数中输出 $x$ 的最小质因子和指数。递归终止条件是当 $x=1$ 时。

【参考代码】

#include <bits/stdc++.h>
using namespace std;

void dfs(int x) {
    if (x == 1) return;
    for (int i = 2; i <= x; i++) {
        if (x % i == 0) {
            int num = 0;
            while (x % i == 0) {
                num++;
                x /= i;
            }
            if (x == 1) {
                if (num == 1) cout << i;
                else cout << i << "^" << num;
            }
            else {
                if (num == 1) cout << i;
                else cout << i << "^" << num;
                cout << "*";
            }
            break;
        }
    }
    dfs(x);
}
int main() {
    int n;
    cin >> n;
    dfs(n);
    return 0;
}

【时间复杂度】

$O(n)$

【预计得分】

$100pts$