ZeroJudge 解題筆記：d121. 00583 - Prime Factors

作者：王一哲
日期：2026年4月15日


ZeroJudge 題目連結：d121. 00583 - Prime Factors

解題想法

因為 $n$ 的上限為 $2^{31}$，質因數的上限為 $\sqrt{2^{31}} \approx 46340$，可以先建 $1$ 到 $46340$ 的質數表，然後再用試除法找質因數。不過這題最麻煩的地方，反而是在於要拼出正確的輸出格式。

Python 程式碼

使用時間約為 39 ms，記憶體約為 9.1 MB，通過測試。

def solve():
    import sys
    
    # 建質數表，1 ~ sqrt(2^31)，大約 46340
    maxn = 46340
    sieve = [True]*(maxn + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(maxn**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, maxn + 1, i):
                sieve[j] = False
    primes = [i for i in range(maxn + 1) if sieve[i]]
    
    # 主要的解題過程
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break  # 停止運作的條件
        if n == 1:  # 特例
            result.append("1 = 1\n")
            continue
        factors = []  # 質因數
        m = n  # n 的質先存到 m
        if m < 0:  # 負數
            factors.append(-1)  # 先加入 -1
            m = -m  # 轉為正值
        # 找質因數，m 的值先存到 x
        x = m
        for p in primes:
            if p*p > x:  # 沒有更大的質因數，中止迴圈
                break
            while x%p == 0:
                factors.append(p)
                x //= p
        if x > 1: factors.append(x)
        # 組合答案
        res = " x ".join(map(str, factors))
        result.append(f"{n:d} = {res}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 2 ms，記憶體約為 2.9 MB，通過測試。

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

int main() {
    // 建質數表，1 ~ sqrt(2^31)，大約 46340
    const int maxn = 46340;
    vector<bool> sieve (maxn + 1, true);
    sieve[0] = false;
    sieve[1] = false;
    for(int i=2; i<=(int)sqrt(maxn); i++) {
        if (sieve[i]) {
            for(int j=i*i; j<=maxn; j+=i) {
                sieve[j] = false;
            }
        }
    }
    vector<int> primes;
    for(int i=0; i<=maxn; i++) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
    
    // 主要的解題過程
    int n;
    while(scanf("%d", &n) != EOF && n != 0) {
        if (n == 1) {  // 特例
            puts("1 = 1");
            continue;
        }
        bool first_item = true;
        printf("%d = ", n);
        if (n < 0) {  // 負數
            printf("-1");  // 先印出 -1
            first_item = false;
            n = -n;  // 轉為正值
        }
        // 找質因數
        for(int p : primes) {
            if (p*p > n) {  // 沒有更大的質因數，中止迴圈
                break;
            }
            while(n%p == 0) {  // p 是質因數
                if (first_item) {
                    printf("%d", p);
                    first_item = false;
                } else {
                    printf(" x %d", p);
                }
                n /= p;
            }
        }
        if (n > 1) {
            if (first_item) printf("%d\n", n);
            else printf(" x %d\n", n);
        } else {
            printf("\n");
        }
    }
    return 0;
}