最大公約数・最小公倍数を求める(ユークリッドの互除法)

このレッスンでは、Kotlinでユークリッドの互除法を使って最大公約数・最小公倍数を求める方法を学び、再帰を使った数学的アルゴリズムを理解することを目標にします。「Kotlin 最大公約数最小公倍数実装」で調べている方向けです。

ユークリッドの互除法は、2つの数の最大公約数(GCD)を効率よく求める古代からのアルゴリズムです。「大きい方を小さい方で割った余りで、また同じ計算を繰り返す」を余りが0になるまで続けます。

サンプルコードでは、gcd()関数が式形式のメソッドを使い、if (b == 0) a else gcd(b, a % b)という1行で再帰処理を表現しています。最小公倍数はa * b / gcd(a, b)という関係から、lcm()で最大公約数の結果を利用して求めています。

初心者がよくつまずくのが、最大公約数と最小公倍数の関係を知らないことです。最大公約数さえ求まれば、掛け算と割り算だけで最小公倍数も簡単に求められます。

再帰関数の練習題材としても非常によく使われる、数学とプログラミングの両方の基礎が詰まった有名なアルゴリズムです。

📖 お手本コード

fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
fun lcm(a: Int, b: Int): Int = a * b / gcd(a, b)

fun main() {
    println("最大公約数: ${gcd(12, 18)}")
    println("最小公倍数: ${lcm(4, 6)}")
}

✍️ あなたのコード

コードを書いたら「実行する」を押してください

🧪 このサイトではKotlinを直接コンパイル・実行できないため、お手本コードと同じ内容を入力できたかをその場で判定します(採点はブラウザ内だけで行われ、どこにも送信されません)。

🎯

ここまでできればゴール達成!
分数を約分するような、ミニ計算ツールが作れるようになります。