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

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

ユークリッドの互除法は、2つの数の最大公約数を効率よく求める古典的なアルゴリズムです。「大きい数を小さい数で割った余りとの最大公約数は、元の2数の最大公約数と等しい」という性質を利用して、再帰的に計算します。

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

初心者がよくつまずくのが、最大公約数と最小公倍数の関係を知らず、最小公倍数を1から別のロジックで計算しようとしてしまうことです。最大公約数さえ求まれば、掛け算と割り算だけで最小公倍数も簡単に求められます。

実際の開発現場では、分数の約分や、周期の異なる処理が同時に発生するタイミングの計算など、数学的な処理を行う場面でこのアルゴリズムの考え方が応用されます。