最大公因數( 多個數字) - Python 教學

基本原理. 要求出有多個數字的最大公因數，最簡單的方法就是先將「最小的數字」當作「暫定的 ... 最大公因數(多個數字) 這篇文章會介紹使用Python的串列操作、排序、for迴圈和if判斷式，讓使用者輸入多個數字後，自動計算出這幾個數字的最大公因數。

本篇使用的Python版本為3.7.12，所有範例可使用GoogleColab實作，不用安裝任何軟體(參考：使用GoogleColab) 什麼是最大公因數？ 「最大公因數」也稱作「最大公約數」，表示能夠「整除多個整數的最大正整數」，例如12、24、48這三個數字的最大公因數是12，又例如222、333、999999這三個數字的最大公因數是111。

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

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

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

input_str=input('輸入數字(逗號分隔)：')#讓使用者輸入數字，數字間用逗號分隔 nums_arr=input_str.split(',')#將輸入的文字，用逗號拆分成串列 foriinrange(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] foriinrange(2,result+1):#使用for迴圈，找出result數字的每個因數 ifresult%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從大到小排序 forjinarr:#依序取出arr串列中的每個數字 a=0#建立a變數，記錄餘數 output=1#建立output變數，記錄最大公因數(預設1) foriinnums_arr:#依序將輸入的數字除以arr串列中的數字 a=a+i%j#將餘數加入a變數(如果沒有餘數，a就一直會是0) output=j#將output等於目前的因數 ifa==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)foriininput().split(',')]#使用生成式將輸入的數字變成串列 nums.sort()#由小到大排序 result=nums[0]#取出最小的項目當作預設的最大公因數 whileresult!=1:#如果result不為1，就不斷執行迴圈內容 foriinrange(1,len(nums)):#使用for迴圈，依序將串列元素取出執行 r=nums[i]%result#取得相除後的餘數 ifr!=0:#如果相除後餘數不為0 nums.insert(0,r)#將餘數插入為串列的第一個項目 break#只要遇到餘數不為0就跳出迴圈 ifresult!=nums[0]:#如果result不等於串列第一個項目(餘數) result=nums[0]#將result改為第一個項目(餘數)，然後重新執行while迴圈 else: break#如果相等，表示沒有餘數，得到最大公因數 print(result) Python教學 基本介紹 關於Python 使用GoogleColab 使用Anaconda 資料型別 變數variable 變數(全域、區域) 數字number 文字與字串string 文字與字串(常用方法) 文字與字串(格式化) 串列list 串列(常用方法) 元組/數組tuple 字典dictionary 集合set 語法觀念 縮排和註解 運算子operator 邏輯判斷(if、elif、else) 邏輯判斷(and和or) 重複迴圈(for、while) 例外處理(try、except) 生成式comprehension 匯入模組import 函式操作 函式function 匿名函式lambda 遞迴recursion 產生器generator 裝飾器decorator 閉包closure 物件與類別 類別class 繼承inheritance 內建函式/方法 輸入與輸出 數學計算 字串操作與轉換 迭代物件轉換 迭代物件操作 檔案讀寫(open) eval()與exec() 標準函式庫/模組 隨機數random 數學math 時間與日期datetime 時間處理time 日曆calendar 使用正規表達式re 檔案操作os 查找匹配檔案glob 高階檔案操作shutil 高效迭代器itertools CSV檔案操作 JSON檔案操作 concurrent.futures 網路爬蟲 關於網路爬蟲 破解反爬蟲的方法 Requests函式庫 BeautifulSoup函式庫 Selenium函式庫 爬取PTT文章標題 自動下載PTT正妹圖片 同時下載多張圖片 爬取空氣品質指標(AQI) 發送LINENotify通知 LINENotify雷達回波圖 爬取臺灣銀行牌告匯率 爬取Yahoo股市即時股價 爬取LINETODAY留言 批次下載Pinterest圖片 登入Mobile01截圖下載 Twitter自動上傳圖文 基礎範例 攝氏/華氏轉換 公分/英吋換算 判斷平年與閏年 找出不重複字元 找出中間的字元 大樂透電腦選號 下載進度條 星號金字塔 數字金字塔 猜數字(猜大猜小) 猜數字(幾A幾B) 計算BMI數值 計算年紀(歲、月、天) 產生身分證字號(隨機) 檢查身分證字號 羅馬數字轉換 數學範例 兩個數字的四則運算 計算多個數字的總和 費波那契數列 九九乘法表 質因數分解 快速找出質數 最小公倍數(多個數字) 最大公因數(多個數字) 實用範例 定時自動螢幕截圖 LINENotify傳送螢幕截圖 批次重新命名檔案 批次圖片轉檔 批次調整圖片尺寸 圖片加上logo浮水印 圖片加上文字浮水印 裁切與旋轉圖片 讀取與修改圖片Exif ZeroJudge解答 關於ZeroJudge a001:哈囉 a002:簡易加法 a003:兩光法師占卜術 a004:文文的求婚 a005:Eva的回家作業 a006:一元二次方程式 a009:解碼器 a010:因數分解 a013:羅馬數字 a015:矩陣的翻轉 a017:五則運算 a020:身分證檢驗 a021:大數運算 a022:迴文 a024:最大公因數(GCD) a034:二進位制轉換 a038:數字翻轉 a040:阿姆斯壯數 a042:平面圓形切割 a044:空間切割 a053:Sagit's計分程式 a054:電話客服中心 a058:MOD3 a059:完全平方和 a065:提款卡密碼 a095:麥哲倫的陰謀 a104:排序 a147:Printitall a148:YouCannotPass?! a149:乘乘樂 a215:明明愛數數 a216:數數愛明明 a224:明明愛明明 a225:明明愛排列 a244:新手訓練~for+if a248:新手訓練~陣列應用 a263:日期差幾天 a410:解方程 a524:手機之謎 d073:分組報告 e267:GroupReverse d294:算算算Easy