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

このレッスンでは、ユークリッドの互除法を使って最大公約数と最小公倍数を求める方法を学び、再帰関数の基本を体験することを目標にします。「Python 最大公約数 求め方」「Python math.gcd」で調べている方向けです。

ユークリッドの互除法は、2つの数の最大公約数(GCD)を効率よく求める古代からのアルゴリズムです。Pythonにはmath.gcd()という組み込み関数も用意されています。仕組みを知らなくても組み込み関数で実務には十分対応できます。

サンプルコードでは、math.gcd(12, 18)で最大公約数を求め、その結果を使ってlcm関数の中で最小公倍数を計算しています。最小公倍数は(a * b) // math.gcd(a, b)という計算式で求められる、最大公約数を使った定番のテクニックです。

初心者がよくつまずくのが、なぜこの計算式で最小公倍数が求まるのかという理屈です。2つの数の積を最大公約数で割ると最小公倍数になる、という数学的な関係を知っておくと、単なる暗記ではなく理解を伴った実装ができます。//で整数の割り算を行っている点にも注目しましょう。

再帰的な考え方を学ぶ練習題材として、数学とプログラミングの両方の基礎が詰まった有名なアルゴリズムです。最小公倍数はこの最大公約数を使って簡単に求められる、セットで覚えておきたい計算です。