今天是最後一堂課了，我們來學一個數學相關的演算法——輾轉相除法。

輾轉相除法又叫做歐幾里德算法，他是目前最常拿來求最大公因數的方法。

作法很簡單，就是兩個數字一直將大的減去小的，當其中一個為零時，另一個就是最終答案。

fun gcd(a:Int,b:Int):Int{
    var x = a
    var y = b
    while(x!=0 && y!=0){
        if(y<x){
            var temp = x
            x = y
            y = temp
        }
        y%=x
    }
    if(y==0){
        return x
    }
    else{
        return y
    }
}

fun main(){
    var a = readln().toInt()
    var b = readln().toInt()
    println("${gcd(a,b)}")

}

那其實我們可以再更加優化一點，如果b比a的n倍還大，那就要減n次a，這個行為其實相等於b%a，所以可以寫成這樣。

fun gcd(a:Int,b:Int):Int{
    var x = a
    var y = b
    while(x!=0 && y!=0){
        if(y<x){
            var temp = x
            x = y
            y = temp
        }
        y-=x
    }
    if(y==0){
        return x
    }
    else{
        return y
    }
}

fun main(){
    var a = readln().toInt()
    var b = readln().toInt()
    println("${gcd(a,b)}")

}

這就是我們的歐幾里德算法的程式碼了。

當然我們也可以寫成遞迴的版本。

fun gcd(a:Int,b:Int):Int{
    if(a==0){
        return b
    }
    else if(b==0){
        return a
    }
    else{
        if(b<a){
            return gcd(b,a)
        }
        else{
            return gcd(b%a,a)
        }
    }
}

這裡簡單解釋一下原理，假設最大公因數是r，a=nr，b=mr，a<b，m跟n互質。

第二輪的b會變成(m-n)r，不斷相減，因為互值，最後 r 的係數就會變成1，那我們的答案就可以取得了。（如果m=n的話，那當然直接代表a=b，所以b%a會等於0，回傳值就是a，一樣是我們的答案）