切換
舊版
前往
大廳
主題

ZeroJudge - e929: pC. 分解質因數 解題心得

Not In My Back Yard | 2020-03-27 01:04:17 | 巴幣 2 | 人氣 277

題目連結:


題目大意:
給定一正整數 N (2 ≦ N ≦ 20000000),請將 N 質因數分解。輸出格式參見範例輸出。



範例輸入:
範例輸入一:
84

範例輸入二:
100

範例輸入三:
97


範例輸出:
範例輸出一:
84 = 2^2 * 3 * 7

範例輸出二:
100 = 2^2 * 5^2

範例輸出三:
97 = 97


解題思維:
就跟判斷一個數是否為質數類似,跑到根號 N 就好。期間每個數字就除除看,除得盡表示當前遇到的數字是質數且是 N 的質因數,因此將 N 去除掉有關該數字的乘積去更新 N 的值。最後的 N 值如果不為 1 代表原本的 N 有一個 > 根號 N 的質因數。照著格式輸出即可。

當然,建一個質數表會使上面的過程省去一些不必要的判斷以及動作。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作