最大公因數 ( 多個數字 )

這篇文章會介紹使用 Python 的串列操作、排序、for 迴圈和 if 判斷式，讓使用者輸入多個數字後，自動計算出這幾個數字的最大公因數。

本篇使用的 Python 版本為 3.7.12，所有範例可使用 Google Colab 實作，不用安裝任何軟體 ( 參考：使用 Google Colab )

什麼是最大公因數？

「最大公因數」也稱作「最大公約數」，表示能夠「整除多個整數的最大正整數」，例如 12、24、48 這三個數字的最大公因數是 12，又例如 222、333、999999 這三個數字的最大公因數是 111。

基本原理

要求出有多個數字的最大公因數，最簡單的方法就是先將「最小的數字」當作「暫定的最大公因數」，並將其拆解成「由大到小」的因數，接著將其他所有的數字，依序除以這些因數，如果某個因數能將所有數字整除，這個因數就是最大公因數。

編輯程式

按照最大公因數的原理，編輯程式。

會使用 list()、sort() 排序、split() 拆分字串...等方法操作字串與串列，也會使用 for 迴圈 進行重複的行為。

input_str = input('輸入數字 ( 逗號分隔 )：')     # 讓使用者輸入數字，數字間用逗號分隔
nums_arr = input_str.split(',')               # 將輸入的文字，用逗號拆分成串列
for i in range(len(nums_arr)):                # 將串列的每個項目轉換成文字
    nums_arr[i-1] = int(nums_arr[i-1])
nums_arr.sort()                # 將串列從小到大排序
result = nums_arr[0]           # 建立變數 result，內容為輸入的第一個數字 ( 數字的最小值 )
arr = [result, 1]              # 建立一個變數 arr 為串列，內容預設為 [ 輸入的最小值, 1 ]
for i in range(2,result+1):    # 使用 for 迴圈，找出 result 數字的每個因數
    if result%i == 0:          # 找因數的方法，將 result 依序除以 2、3、4...result
        result = int(result/i) # 如果餘數為 0 ( 整除 )，表示這個數字為因數
        arr.append(i)          # 將因數加入 arr 串列中，並更新 result 為除以因數的數值
        arr.append(result)     # 也將 result 加入 arr 串列 ( 因為商也算是因數 )
arr.sort(reverse=True)         # 完成後將 arr 從大到小排序

for j in arr:                # 依序取出 arr 串列中的每個數字
    a = 0                    # 建立 a 變數，記錄餘數
    output = 1               # 建立 output 變數，記錄最大公因數 ( 預設 1 )
    for i in nums_arr:       # 依序將輸入的數字除以 arr 串列中的數字
        a = a + i%j          # 將餘數加入 a 變數 ( 如果沒有餘數，a 就一直會是 0 )
        output = j           # 將 output 等於目前的因數
    if a == 0:               # 如果 a 為 0 表示都整除，將 result 等於 output
        result = output
        break
print(result)                # 印出最大公因數

使用輾轉相除法找出最大公因數

上面的例子雖然可以找出最大公因數，但因為是使用「窮舉法」( 一個一個找 )，如果要找「大數字」會耗費大量的時間，所以接下來會套用「輾轉相除法」來找出最大公因數。

什麼是輾轉相除法？例如要求 50 和 80 的最大公因數，先以 80 除以 50，得到餘數為30；再以 50 除以 30得到餘數為20；接著以 30 除以 20 得到餘數 10，最後 20 除以 10 的餘數為 0，10 就是最大公因數。更多可以參考：輾轉相除法

參考：串列生成式、算數運算子

nums = [int(i) for i in input().split(',')]   # 使用生成式將輸入的數字變成串列
nums.sort()                         # 由小到大排序
result = nums[0]                    # 取出最小的項目當作預設的最大公因數
while result!=1:                    # 如果 result 不為 1，就不斷執行迴圈內容
    for i in range(1,len(nums)):    # 使用 for 迴圈，依序將串列元素取出執行
        r = nums[i]%result          # 取得相除後的餘數
        if r !=0:                   # 如果相除後餘數不為 0
            nums.insert(0, r)       # 將餘數插入為串列的第一個項目
            break                   # 只要遇到餘數不為 0 就跳出迴圈
    if result != nums[0]:           # 如果 result 不等於串列第一個項目 ( 餘數 )
        result = nums[0]            # 將 result 改為第一個項目 ( 餘數 )，然後重新執行 while 迴圈
    else:
        break                       # 如果相等，表示沒有餘數，得到最大公因數
print(result)

意見回饋

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