C 語言經典算法：正整數質因數分解

題目描述

將一個正整數分解為質因數乘積形式。例如：輸入 90，輸出 90=2*3*3*5。

算法原理

1. 從最小質數 2 開始嘗試除以 n
2. 若能整除，輸出該質因子，用商替換 n，繼續嘗試同一因子
3. 若不能整除，因子加 1（或優化為：2 後只試奇數）
4. 當因子平方大於當前 n 時，剩餘 n 必為質數，直接輸出結束

優化實現（O(√n) 複雜度）

#include <stdio.h>
#include <math.h>

int main(void) {
    long long n;
    printf("請輸入一個正整數：");
    if (scanf("%lld", &n) != 1 || n <= 0) {
        printf("輸入無效。\n");
        return 1;
    }

    printf("%lld=", n);
    long long original = n;
    int first = 1;

    // 處理因子 2
    while (n % 2 == 0) {
        if (!first) printf("*");
        printf("2");
        first = 0;
        n /= 2;
    }

    // 處理奇數因子 3, 5, 7... 直到 sqrt(n)
    for (long long i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            if (!first) printf("*");
            printf("%lld", i);
            first = 0;
            n /= i;
        }
    }

    // 剩餘 n > 1 即為最後一個大質因子
    if (n > 1) {
        if (!first) printf("*");
        printf("%lld", n);
    }

    // 特殊情況：輸入本身為質數或 1
    if (first) {
        if (original == 1) printf("1");  // 1 無質因數分解，按題意輸出 1
        else printf("%lld", original);   // 質數
    }
    printf("\n");
    return 0;
}

關鍵優化點

1. 分離因子 2，後續只遍歷奇數，迭代次數減半
2. 循環條件 i * i <= n，動態縮小上界，避免多餘計算
3. 使用 long long 支持 64 位大整數（< 2^63）
4. 格式化輸出控制，首個因子前不印 *
5. 輸入合法性檢查，工程級健壯性

示例運行

輸入：90
輸出：90=2*3*3*5

輸入：13
輸出：13=13

輸入：1
輸出：1=1

輸入：1000000007
輸出：1000000007=1000000007  (質數)

進階拓展

• Pollard's Rho 算法：大整數（> 10^12）快速分解
• 篩法預計算質數表：批量分解多個數時極快
• 並行分解：多線程/分布式處理超大整數

質因數分解是數論基礎，也是加密學（RSA）安全性的核心。掌握高效試除法，是理解更高級算法的起點。