a010: 因數分解

2019-08-01

內容

各位在國小時都學過因數分解，都瞭解怎麼樣用紙筆計算出結果，現在由你來敎電腦做因數分解。

因數分解就是把一個數字，切分為數個質數的乘積，如 12=2^2 * 3

其中, 次方的符號以 ^ 來表示

輸入

一個整數, 大於 1 且小於等於 1000000

20
17
999997

輸出

一個字串

2^2 _ 5
17
757 _ 1321

解題思路

從 2 開始往上試除，若可以整除輸入值則將輸入值除以試除值，若無則試除值+1，如此循環直至試除值大於剩下的輸入值。

完整程式碼

AC (3ms, 92KB)

#include <stdio.h>

int num, count;
char output[10000], * oPt;

int main()
{
    while (scanf(" %d", &num) == 1)
    {
        oPt = output;
        for (int i = 2; i <= num; i++)
        {
            while (!(num % i))
            {
                num /= i;
                count++;
            }
            if (count)
            {
                if (count == 1)
                    oPt += sprintf(oPt, "%d * ", i);
                else
                    oPt += sprintf(oPt, "%d^%d * ", i, count);
                count = 0;
            }
        }
        *(oPt - 3) = 0;
        puts(output);
    }
    return 0;
}