【Swift】ユークリッドの互除法の実装｜最大公約数の発見

新卒や転職でエンジニアを目指す方で，コーディングテスト対策に取り組んでいますか？
この記事では，コーディングテストでも使うことのあるユークリッドの互除法についてSwiftを用いて解説します！
高校の数学の授業で出てくるあれですね笑

Swiftの勉強を頑張っている方の励みになると嬉しいです！

Contents

ユークリッドの互除法とは
Swiftを用いたユークリッドの互除法
- コード解説
- 活用事例
おわりに

ユークリッドの互除法とは

ユークリッドの互除法とは
2つの自然数の最大公約数（Greatest Common Divisor, GCD）を効率的に求めるためのアルゴリズムです．
高校の数学で習ったやつですね笑

手順としては下記の通りになります・

ユークリッドの互除法の手順

a と b を用意する．
ただし、 a ≧ b であると仮定する（もしa < b ならば a と b を入れ替える）
a を b で割り、商 q と余り r を求める．
つまり、次のように表されます：
a = b × q + r
余り r が 0 であれば、 b が最大公約数となる．
もし r ≠ 0 であれば、 a を b に、 b を r に置き換えて手順2を繰り返す．

手順を書くと上記の通りですが，少し分かりづらいと思います．．
よくわからないという方は以下の例を見ると思い出すのではないでしょうか？？

a = 252 と b = 105 の最大公約数を求めるとする．

252 ÷ 105 = 2 余り 42 （つまり、 252 = 105 × 2 + 42 ）
105 ÷ 42 = 2 余り 21 （つまり、 105 = 42 ×2 + 21 ）
42 ÷ 21 = 2 余り 0 （つまり、 42 = 21 ×2 + 0 ）

余りが0になったので、この時点で最大公約数は21と求まる．

なぜこの手順で最大公約数が求まるのかアルゴリズム・証明の部分までは解説しませんが，
やり方を思い出したでしょうか．

それでは実際にSwiftを用いてどのようにユークリッドの互除法を実装するのかを続いて解説していきます！

Swiftを用いたユークリッドの互除法

コード解説

Swiftを用いてユークリッドの互除法は以下のコードになります．

func gcd(_ x: Int, _ y: Int) -> Int {
    if y == 0 {
        return x;
    } else {
        return gcd(y, x % y);
    }
}

let num1 = 15
let num2 = 5
let gcd = gcd(num1, num2)

Swift

あまりが0となるまで繰り返すことでユークリッドの互除法を実装することができます．

ちなみに，num1≧num2を判別する必要があるのでは？と考えた方もいるのではないでしょうか？
このコードでは実は，その必要がありません．
実際に計算してみると，5÷15=0あまり5 → 15÷5=…のように勝手に入れ替わってくれます．

ただ明示的に表したい場合は．以下のコードに変更すると良いと思います！

func gcd(_ x: Int, _ y: Int) -> Int {
    if x < y {
        return gcd(y, x)  // 入れ替える
    }
    if y == 0 {
        return x
    } else {
        return gcd(y, x % y)
    }
}

let num1 = 15
let num2 = 5
let gcd = gcd(num1, num2)