【Python實作】質因數分解
Python實作＿質因數分解
目的：練習數學運算子、集合
說明：國小的時候有學過因數分解，大概是用短除法吧（我忘了？）。後來國中有了質數的觀念，又補強了一次因數分解，題目開始變得要分解很大的數字。但是人類再怎麼分解也有個極限，不過程式可以分解的值就很大了！本篇就來練習用python質因數分解。
題目：讓使用者輸入一個數字，將該數字切分為數個質數的乘積，如 12=2^2 * 3
（次方的符號以 ^ 來表示）
#程式開始
#質因數分解程式
n = int(input("請輸入一個正整數："))
num = n # 用來之後印結果
factor = 2 # 從最小質數開始
result = {} # 儲存質因數與次方
# 質因數分解
while factor * factor <= n:
while n % factor == 0:
result[factor] = result.get(factor, 0)+1
n //= factor
factor += 1
print(result)
# 若最後 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
{2: 2, 5: 2}
100 = 2^2 * 5^2
（第二次執行）
請輸入一個正整數：1111
{11: 1}
1111 = 11 * 101
（第三次執行）
請輸入一個正整數：5200
{2: 4, 5: 2}
5200 = 2^4 * 5^2 * 13
程式說明
# 質因數分解
while
factor * factor <= n:（外迴圈）：
當factor（質因數，起初為2）的次方小於n的時候，質因數分解就做完了，便跳出迴圈。
因為假如我們要分解的數為25，那麼只要檢查它的質因數到5（25的平方根）即可，因為再往下的話，就會重複。
也可以用math.sqrt()來實現，不過我用平方（比較方便）。
while n % factor == 0: （內迴圈）
result[factor] = result.get(factor, 0)+1
n //= factor
factor += 1
當n可以整除質因數factor的時候，就把result裡面代表factor的key抓出來，然後針對它的值（Value）做運算。
result.get(factor, 0)，result.get是去字典裡面抓factor的值，假如抓不到就建立一個factor的key，然後Value回傳0。最後+1再丟給result[factor]裡面。
當n不能整除質因數factor的時候，那麼factor就+1，然後再丟回外迴圈檢查。
while factor * factor <= n:
while n % factor == 0:
result[factor] = result.get(factor, 0)+1
n //= factor
factor += 1
用12來跑一次這個迴圈試試：
→因為2*2=4，而4<=12，符合外外迴圈條件，進到內迴圈
→ 12可以整除2，進到下一步
→ result.get(2,
0)，由於字典裡面沒有2這個key，所以回傳0，然後+1，丟到result[factor]，也就是result｛2:1｝。
→12/2=6，回到內迴圈
→6可以整除2，進到下一步
→ result.get(2,
0)，由於字典裡面有2這個key，回傳它的值（剛剛已經變成1），然後+1，丟到result[factor]
，也就是result｛2:2｝
→6/2=3，回到內迴圈
→3/2不能整除，跳到
factor += 1
→factor=3，跳到外迴圈
→3*3=9，9<3，外迴圈結束
跑完這個迴圈的結果是：result｛2:2｝，且n=3
最後留下來的n假如不是1，那麼必定是質因數，那麼也要把它的1次方丟到字典裡面。在這個例子當中就是3。
所以我們要再把3進去：
if n > 1:
result[n] = result.get(n, 0) + 1
最後字典裡面就是：result｛2:2,3:1｝
output = []
→準備一個容器，裝最後要顯示的字串。
for p, exp in result.items():
→ 用for迴圈依序把result.items()裡面的元素抓出來
if
exp == 1:
output.append(f"{p}")
→假如exp（result裡面的value，也就是次方數）是1的話，那就直接顯示p就好，因為1次方沒有意義。3^1就是3，那output裡面填入3就好。
else:
output.append(f"{p}^{exp}")
→假如exp不是1的話，那output裡面就填入{p}^{exp}
print(f"{num} = " + " *
".join(output))
" * ".join(output)的意思是：用 " * " 把 output 裡的每個字串串起來。
→ 經過剛剛的填入，output裡面現在是["2^2", "3"]，用字串＂*＂把他們接起來就是2^2 * 3
留言
張貼留言