C語言練習實例14：正整數分解質因數（試除法）

輸入正整數 n，分解質因數並以 n=因子1*因子2*... 格式輸出。如 90=2*3*3*5。

算法

• 從最小質數 2 開始試除。
• 若 n%i==0，輸出 i，n/=i，繼續試除同一 i（處理重複因子）。
• 否則 i++ 試下一個數。
• 直到 i>n 結束。

源代碼

// Created by www.runoob.com on 15/11/9.
// Copyright © 2015年 菜鳥教程. All rights reserved.
//
#include <stdio.h>

int main() {
    int n, i;
    printf("請輸入整數：");
    scanf("%d", &n);
    printf("%d=", n);
    for (i = 2; i <= n; i++) {
        while (n % i == 0) {
            printf("%d", i);
            n /= i;
            if (n != 1) printf("*");
        }
    }
    printf("\n");
    return 0;
}

運行示例

請輸入整數：90
90=2*3*3*5

優化

試除上限可優化至 sqrt(n)，但需處理剩餘 n>1 的情況（即為大質因子）。