C語言實作：整數質因數分解（輸出指數形式）

質因數分解：標準指數形式輸出

本程式將輸入的正整數分解為質因數乘積形式，並以 質因子(指數) 格式輸出。例如 60 = 2² × 3¹ × 5¹ 輸出為 60==2(2)3(1)5(1)。

演算法步驟

1. 保存原始輸入 begin_num 供輸出用。
2. 遍歷潛在質因子 mark：從 2 開始，之後只檢查奇數 (3,5,7...)。
3. 當 mark × mark > num 可提前結束（但原碼條件為 2*i-1 < num 較寬鬆）。
4. 若 num % mark == 0，記錄 mark 並用 while 反覆除盡，計數指數。
5. 最後若 num > 1，剩餘 num 本身為質因子（大質數）。

完整程式碼

#include <stdio.h>

int main()
{
    int i, j = 0;
    int begin_num, num, mark;
    int factor[100], exponent[100] = {0};

    printf("please enter a number:");
    scanf("%d", &num);
    begin_num = num;

    for(i = 1; 2*i - 1 < num; i++)
    {
        mark = 2*i - 1;
        if(mark == 1) mark = 2;  // 2 是唯一偶質數

        if(num % mark == 0)
        {
            factor[j] = mark;
            while(num % mark == 0)
            {
                num /= mark;
                exponent[j]++;
            }
            j++;
        }
    }

    // 處理剩餘大質數（原碼缺少此步驟）
    if(num > 1)
    {
        factor[j] = num;
        exponent[j] = 1;
        j++;
    }

    for(i = 0; i < j; i++)
    {
        if(i == 0) printf("%d==", begin_num);
        printf("%d(%d)", factor[i], exponent[i]);
        if(i == j - 1) printf("\n");
    }
    return 0;
}

執行結果示意

測試案例

原始碼缺陷與修正

• 缺少剩餘大質數處理：若輸入 14=2×7，迴圈除盡 2 後 num=7，條件 2*i-1 < 7 仍會檢查 3,5 但漏掉 7。需在迴圈後加入 if(num>1) 處理。
• 迴圈上限不精確：建議改為 mark * mark <= num。
• 輸入 1 特判：1 無質因數分解，可特殊輸出 1==1(1) 或提示。

改進版核心邏輯

for(mark = 2; mark * mark <= num; mark = (mark==2)?3:mark+2)
{
    if(num % mark == 0) { ... }
}
if(num > 1) { factor[j]=num; exponent[j]=1; j++; }