a010: 因數分解

這篇教學會示範 ZeroJudge 基礎題庫「a010: 因數分解」的解題過程。

題目需求

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

題目連結：a010: 因數分解

解答

這題除了基本的因數分解，重點在於分解後如果有重複的因數，需使用「幾次方」的方式來表現。首先使用進行「因數分解」，並使用一個字典 result 記錄，將取得的因數設為 key，次數設為 value。

參考：字典 dictionary、重複迴圈 ( for、while )、使用 in 檢查鍵、除法取整數

num = int(input())                         # 將輸入的文字轉成數字
result = {}                                # 建立空字典 result
while True:                                # 不斷重複
    for i in range(2, num+1):              # 取出 2～num 的每個數字
        if num%i == 0:                     # 如果 num 除以 i 能整除
            if i in result:
                result[i] = result[i] + 1  # 使用 result 記錄 i 的次數
            else:
                result[i] = 1              # 如果 result 還沒有 key 等於 i
                num = num//i                   # num 等於 num 除以 i 取整數 ( 單純用除以會變成 float )
                break
        if num == 1:                           # 如果 num 等於 1，表示取值結束
            break
    print(result)

程式執行後，如果輸入的數字為 13880，會看見因數為三個 2、一個 5 和一個 347。

已經能分解出因數以及因數的數量後，再根據題目，印出指定的格式，當中建立一個 output 變數作為輸出的文字，使用 for 迴圈將 result 變數的內容轉變成指定的格式，並存入 output 變數裡，最後使用 [:-2] 的方式去除最後兩個字元，就是最後的答案。

串列、讀取串列項目

while True:
    try:
        num = int(input())
        result = {}
        while True:
            for i in range(2, num+1):
                if num%i == 0:
                    if i in result:
                        result[i] = result[i] + 1
                    else:
                        result[i] = 1
                        num = num//i
                    break
            if num == 1:
                break

        output = ''                 # 建立 output 變數為空字串
        for i in result:            # 取出 result 的每個 key 與 value
            if result[i] != 1:      # 如果 key 的 value 不為 1，表示需要使用「次方」表現
                output = f'{output}{i}^{result[i]} * '  # 使用次方表現
            else:
                output = f'{output}{i} * '   # 單純只有一個數字
        output = output[:-2]        # 去除結尾的空白與星號
        print(output)
    except:
        break

意見回饋

如果有任何建議或問題，可傳送「意見表單」給我，謝謝～