# a024 - 最大公因數(GCD)

### 題目連結: [a024](https://zerojudge.tw/ShowProblem?problemid=a024)

### 題目解析
* 輸入兩個整數，利用程式撰寫求得這兩個數字的最大公因數

### 題目類型
數學/迴圈/函式/遞迴邏輯/流程控制

### 範例測資解讀
* 輸入
* 兩個整數均大於 0，也就是非 0 的正整數
* 正整數的範圍最大到 `2的31次方 = 2147483648`
* 輸出
* 輸出兩個整數的最大公因數

### 其他注意事項
* 在程式中求最大公因數的想法為 ==輾轉相除法==

### 程式解析
* 首先要先了解如何在程式中實現輾轉相除法

以 GCD(12,15) 為例，輾轉相除法的計算流程為
1. $15/12 = 1 ... 3$
2. $12/ 3 = 4 ... 0$

因此最大公因數為 `3`

從上述的計算流程可以發現輾轉相除法有以下特性：
* 較大的數字除以較小的數字
* 除數在下一輪會變成被除數、餘數會變成除數
* 當發生整除的時候，最後的除數即為最大公因數

因此我們可以寫成這樣的程式計算過程

while True:
    if a<b:
        # swap(a,b) 兩個變數的值
        a, b = b, a
    
    if b!=0:
        c = a%b
        a = b
        b = c
    else:
        break

設計一個無限迴圈 while True
反覆調整 a, b, c 三個變數的值，其中 a, b, c 為被除數、除數和餘數的關係
進行餘數計算前必須先判斷 a, b 兩數的大小，若發生 a<b 的情況
則需要將 a,b 兩數進行交換(swap)

### 完整程式碼 (僅提供參考)

def GCD(a, b):
    while True:
        if a<b:
            a, b = b, a
        
        if(b != 0):
            c = int(a%b)
            a = b
            b = c
        else:
            break
    # 若滿足 break 條件，則 a 經過 Line8 調整後會是最大公因數
    return a

#start
s = input()
data = s.split()

a = int(data[0])
b = int(data[1])

r = GCD(a, b)

print(r)

###### tags: `基礎15題解` `APCS` `ZeroJudge`