ETH官方钱包

切換
舊版
前往
大廳
主題

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

Not In My Back Yard | 2020-03-27 01:04:17 | 巴幣 2 | 人氣 346
題目連結：
題目大意：
給定一正整數 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 的質因數。照著格式輸出即可。

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

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

作者相關創作

更多創作