ZeroJudge 解題筆記：a010. 因數分解

作者：王一哲
日期：2025年6月22日


ZeroJudge 題目連結：a010. 因數分解

解題想法

因為測資 n 不大，依序測試 2 ~ n 是否為因數，如果這個數字 i 是因數就繼續除下去，同時將 n 縮小為 n/i，直到 n 不能被整除為止，就能夠得到因數及對應的次方。

Python 程式碼

使用時間約為 0.3 s，記憶體約為 3.3 MB，通過測試。

n = int(input())  # 要測試的數
ans = []  # 答案
fac = 2  # 要測試的因數，從 2 開始
""" 找因數及次方 """
while n > 1 and fac <= n:  # 如果 n 大於 1 且 fac 小於等於 n，還可以分解，繼續執行
    cnt = 0  # 次方
    while n%fac == 0:  # 如果 n 可以被 fac 整除，繼續執行
        cnt += 1; n //= fac  # 次方加 1，n 變為除以 fac 的值
    if cnt == 1:  # 如果次方等於 1
        ans.append(f"{fac:d}")  # ans 加入 fac
    elif cnt > 1:  # 如果次方大於 1
        ans.append(f"{fac:d}^{cnt:d}")  # ans 加入 fac 及次方
    fac += 1  # fac 加 1
""" 輸出答案 """
if not ans: print(n)  # 如果 ans 是空的，n 是質數，印出 n
else: print(" * ".join(ans))  # 反之，用 " * " 連接 ans 再輸出

C++ 程式碼

使用時間約為 4 ms，記憶體約為 348 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 要測試的數
    string ans = "";  // 答案
    int fac = 2;  // 要測試的因數，從 2 開始
    /* 找因數及次方 */
    while(n > 1 && fac <= n) {  // 如果 n 大於 1 且 fac 小於等於 n，還可以分解，繼續執行
        int cnt = 0;  // 次方
        while(n%fac == 0) {  // 如果 n 可以被 fac 整除，繼續執行
            cnt++; n /= fac;  // 次方加 1，n 變為除以 fac 的值
        }
        if (cnt == 1) {  // 如果次方等於 1
            if (ans.empty()) ans += to_string(fac);
            else ans += " * " + to_string(fac);
        } else if (cnt > 1) {  // 如果次方大於 1
            if (ans.empty()) ans += to_string(fac) + "^" + to_string(cnt);  // ans 加入 fac 及次方
            else ans += " * " + to_string(fac) + "^" + to_string(cnt);
        }
        fac++;  // fac 加 1
    }
    /* 輸出答案 */
    if (ans.empty()) cout << n << "\n";  // 如果 ans 是空的，n 是質數，印出 n
    else cout << ans << "\n";
    return 0;
}