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

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

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

サンプルコードでは、gcd_func()関数がb == 0になるまでgcd_func(b, a %% b)という形で自分自身を呼び出し続けています。最小公倍数は(a * b) / gcd_func(a, b)という関係から、lcm_func()で最大公約数の結果を利用して求めています。

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

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

📖 お手本コード

gcd_func <- function(a, b) {
  if (b == 0) return(a)
  gcd_func(b, a %% b)
}

lcm_func <- function(a, b) {
  (a * b) / gcd_func(a, b)
}

cat("最大公約数:", gcd_func(12, 18), "\n")
cat("最小公倍数:", lcm_func(4, 6), "\n")

✍️ あなたのコード

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

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

🎯

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