【Python實作】質因數分解
Python 實作｜質因數分解
這篇文章要用 Python 來練習一個很經典的數學題目： 質因數分解。從國小短除法，到國中學質數，我們都曾經手算過這類題目。 不過當數字變大時，人類的耐心通常會先分解掉，這時候就交給程式處理吧。
練習重點：數學運算子、迴圈、字典 Dictionary、字串組合
題目說明
讓使用者輸入一個正整數，程式將該數字分解成數個質數的乘積。
例如：
12 = 2^2 * 3
這裡的次方符號使用 ^ 表示。
完整程式碼
以下是完整的 Python 質因數分解程式：
# 質因數分解程式
n = int(input("請輸入一個正整數："))
num = n # 保留原本輸入的數字，最後輸出結果時會用到
factor = 2 # 從最小的質數 2 開始嘗試
result = {} # 用字典儲存質因數與次方數
# 進行質因數分解
while factor * factor <= n:
while n % factor == 0:
result[factor] = result.get(factor, 0) + 1
n //= factor
factor += 1
# 如果最後剩下的 n 大於 1，表示它本身也是一個質因數
if n > 1:
result[n] = result.get(n, 0) + 1
# 整理輸出格式
output = []
for p, exp in result.items():
if exp == 1:
output.append(f"{p}")
else:
output.append(f"{p}^{exp}")
# 印出結果
print(f"{num} = " + " * ".join(output))執行結果
下面用幾組數字測試看看。
第一次執行
請輸入一個正整數：100
100 = 2^2 * 5^2第二次執行
請輸入一個正整數：1111
1111 = 11 * 101第三次執行
請輸入一個正整數：5200
5200 = 2^4 * 5^2 * 13程式說明
這支程式的核心概念很單純： 從 2 開始嘗試除輸入的數字，只要可以整除，就代表找到一個質因數。 每除一次，就把該質因數的次方數加一。
一、準備變數
n = int(input("請輸入一個正整數："))
num = n
factor = 2
result = {}n：使用者輸入的數字，之後會不斷被除小。num：保留原始輸入值，最後輸出結果時使用。factor：目前嘗試的因數，從 2 開始。result：用來記錄質因數與次方數。
二、外層迴圈：檢查到平方根即可
while factor * factor <= n:
這裡使用 factor * factor <= n，
意思是只需要檢查到目前數字的平方根為止。
例如要分解 25，只需要檢查到 5 就好。 因為如果一個數字有超過平方根的因數，那麼一定會搭配一個小於平方根的因數，前面早就會被檢查到了。
小提醒：這裡也可以用 math.sqrt()，
但直接使用平方比較簡潔，也可以避免浮點數誤差。
三、內層迴圈：只要可以整除，就一直除
while n % factor == 0:
result[factor] = result.get(factor, 0) + 1
n //= factor
如果 n % factor == 0，
代表目前的 factor
可以整除 n，
也就是它是其中一個質因數。
接著這一行會把質因數出現的次數加一：
result[factor] = result.get(factor, 0) + 1
result.get(factor, 0)
的意思是：
- 如果字典裡已經有這個
factor，就取出它原本的次方數。 - 如果還沒有，就先當作 0。
- 最後再加 1，表示這個質因數又出現了一次。
然後使用整數除法：
n //= factor
這行會把 n
除以目前的質因數，並更新成新的值。
四、換下一個因數
factor += 1
當目前的 factor
已經不能再整除 n，
就讓 factor 加一，
繼續檢查下一個可能的因數。
用 12 實際跑一次
假設輸入的數字是 12，程式會這樣運作：
- 一開始
n = 12，factor = 2。 2 * 2 <= 12，符合外層迴圈條件。- 12 可以被 2 整除，所以記錄一次 2，得到
result = {2: 1}。 - 將 12 除以 2，得到
n = 6。 - 6 仍然可以被 2 整除，所以再記錄一次 2，得到
result = {2: 2}。 - 將 6 除以 2，得到
n = 3。 - 3 不能被 2 整除，所以
factor加一，變成 3。 - 此時
3 * 3 <= 3不成立，外層迴圈結束。
迴圈結束後，目前結果是：
result = {2: 2}
n = 3
最後剩下的 n = 3
大於 1，代表它本身也是一個質因數，所以要再放進字典：
if n > 1:
result[n] = result.get(n, 0) + 1最後得到：
result = {2: 2, 3: 1}整理輸出格式
字典裡雖然已經有答案，但直接印出字典不太像數學表示式。 所以最後要把它整理成比較好看的格式。
output = []
for p, exp in result.items():
if exp == 1:
output.append(f"{p}")
else:
output.append(f"{p}^{exp}")這段程式會逐一取出字典中的質因數與次方數。
- 如果次方數是 1，就只顯示質因數本身，例如
3。 - 如果次方數大於 1，就顯示成
2^2這種格式。
最後用 " * ".join(output)
把每一個質因數用乘號串起來：
print(f"{num} = " + " * ".join(output))
如果 output
裡面是：
["2^2", "3"]那麼最後就會輸出：
12 = 2^2 * 3小結
這次的質因數分解練習，主要用到了幾個 Python 基礎觀念：
- 取餘數運算子：使用
%判斷是否可以整除。 - 整數除法：使用
//更新被分解的數字。 - while 迴圈：重複檢查每一個可能的因數。
- 字典 Dictionary：儲存質因數與出現次數。
- 字串組合：用
join()組成最後的數學表示式。
這類題目看起來是數學，其實很適合拿來練習程式邏輯。 因為它需要判斷、重複執行、記錄結果，最後再整理輸出。 換句話說，這題雖然叫質因數分解，但它其實也偷偷分解了不少 Python 基礎能力。
留言
張貼留言