a010. 因數分解

題目連結

https://zerojudge.tw/ShowProblem?problemid=a010

解題思路

這題的關鍵是「因數分解」這四個字，背後所代表的計算過程。當我們在做因數分解的時候，會使用短除法，從最小的質數開始檢查。當遇到該數的因數時，就把該數除以此質數得到商數，然後再重複上述動作，直到確定商數已經不能再被此質數整除為止。重複上述動作直到商數剩下一為止，即完成因數分解。

注意事項

在因數分解時，因數之間會以 * 隔開，但注意輸出結尾不會有 * 。因此，我們必須判斷甚麼時候輸出結束。而正如解題思路所說，因數分解到最後，商數會剩下一。因此，我們可以利用if條件句判斷，當商數不為一的時候再輸出 * 。

程式碼：C語言

#include <stdio.h>
int main() {
    //宣告並讀取變數num，代表要進行因數分解的整數
    int num;
    scanf("%d", &num);
    //用for迴圈跑2到自己本身的所有數字，檢查是否為因數
    for(int factor = 2 ; factor <= num ; factor++) {
        //若可以整除，代表此數是因數，將其分解至得出質因數為止
        if(num%factor == 0) {
            int power = 0;
            while(num%factor == 0) {
                num /= factor;
                power++;
            }
            //若此質因數只有一次，直接輸出數字即可
            if(power == 1)
                printf("%d", factor);
            //若此質因數不只一次，需輸出共幾次方
            else
                printf("%d^%d", factor, power);
            //除了最後一位以外，每個質因數輸出後皆須加上*
            if(num != 1)
                printf(" * ");
        }
    }
    return 0;
}