a024: 最大公因數 ( GCD )

這篇教學會示範 ZeroJudge 基礎題庫「a024: 最大公因數 ( GCD )」的解題過程。

題目需求

題目會給定兩個整數，透過程式求出它們的最大公因數。

題目連結：a024: 最大公因數 ( GCD )

解答

參考「最大公因數 ( 多個數字 )」教學，使用輾轉相除法，就能找出最大公因數。

參考：最大公因數 ( 多個數字 )

while True:
  try:
    nums = [int(i) for i in input().split(' ')]  # 將輸入的文字轉成數字串列
    nums.sort()             # 從小到大排序數字串列
    result = nums[0]        # 先設定最小值為最大公因數 result
    while result!=1:        # 如果 result 不等於 1，就不斷重複執行
      r = nums[1]%result    # 將第二個數字除以 result 算出餘數
      if r !=0:             # 如果有餘數
        result = r          # 將 result 設為餘數
        nums.insert(0,r)    # 將餘數放在串列的第一個項目，然後再來一次
      else:
        break               # 如果餘數為 0，表示找到最大公因數，停止迴圈
    print(result)
  except:
    break

意見回饋

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