最大公因数 ( 多个数字 )

这篇文章会介绍使用 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)

意见反馈