PAT 1059 Prime Factors - 長整數質因子分解輸出格式化

問題描述

給定正整數 N（long int 範圍），分解質因子並按格式輸出：N = p1^k1 * p2^k2 * ... * pm^km。質因子遞增，指數為 1 時省略 ^1。

範例： 97532468 = 2^2 * 11 * 17 * 101 * 1291

解題思路：試除法分解

從 2 開始枚舉到 sqrt(N)，每個質數反覆除盡，記錄指數。剩餘 N > 1 即為最後一個大質因子。

C++ 完整代碼

#include 
#include 
using namespace std;

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

int main() {
    long long n; scanf("%lld", &n);
    printf("%lld=", n);
    
    if (n == 1) { printf("1\n"); return 0; }
    
    for (long long p = 2; p * p <= n; ++p) {
        if (!isPrime(p)) continue;  // 可優化：直接枚舉所有數，非質數不會整除
        int cnt = 0;
        while (n % p == 0) {
            ++cnt; n /= p;
        }
        if (cnt > 0) {
            printf("%lld", p);
            if (cnt > 1) printf("^%d", cnt);
            if (n > 1) printf("*");
        }
    }
    if (n > 1) printf("%lld", n);  // 剩餘大質因子
    printf("\n");
    return 0;
}

優化版：無需額外質數判斷

直接枚舉 i = 2..sqrt(n)，若 i 能整除則必為質數（因為更小的質因子已被除盡）。

int main() {
    long long n; scanf("%lld", &n);
    printf("%lld=", n);
    if (n == 1) { puts("1"); return 0; }
    
    bool first = true;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { ++cnt; n /= i; }
            if (!first) printf("*");
            first = false;
            printf("%lld", i);
            if (cnt > 1) printf("^%d", cnt);
        }
    }
    if (n > 1) {
        if (!first) printf("*");
        printf("%lld", n);
    }
    puts("");
    return 0;
}

關鍵點總結

1. 試除上界：i * i <= n 動態縮小，因為 n 不斷被除小
2. 格式控制：首因子前無 *，指數 1 省略 ^1
3. 長整數：用 long long / %lld 處理 32 位有號整數範圍
4. 特例 N=1：直接輸出 1=1

複雜度分析

• 時間：O(√N) 最壞情況（N 為大質數）
• 空間：O(1)

對於 2^31-1 級別數值，試除法完全足夠。