Pythonでユークリッドの互除法を使って最大公約数を求める
このレッスンでは、ユークリッドの互除法で2つの数の最大公約数(GCD)を求めます。
はじめに
どんな問題を解決するか
分数を約分するとき、ものを同じ大きさのグループに分けるとき、そして多くのパズルで、2つの数の両方を割り切る最大の数が必要になります。候補を1つずつすべて試す方法は、数が大きいと時間がかかります。ユークリッドは2,000年以上前に、ずっと速い方法を見つけました。
身近なたとえ
ユークリッドの方法は、長方形をできるだけ大きな正方形のタイルで敷き詰めるようなものです。48 × 18 の長方形から、切り取れるいちばん大きな正方形を切り取り、残った部分からも同じように切り取っていきます。余りが出ずにぴったり切り分けられたら、最後の正方形の一辺が答えです。
first, second▭ 長方形:48 × 18first % second✂️ 短い辺を一辺とする正方形を切り取った残りfirst, second = second, first % second🔁 残った部分で同じことを繰り返すwhile second:✅ 余りなし:その一辺が最大公約数の62つの整数の最大公約数(GCD)は、その両方を割り切る最大の正の整数です。ユークリッドの互除法では、b が0になるまで、組 (a, b) を (b, a % b) に置き換えることを繰り返して求めます。
重要なポイント
first, second = second, first % secondで、2つの数の組を、小さいほうの数と余りの組に置き換えます。- 48と18では、組は (48, 18)、(18, 12)、(12, 6)、(6, 0) と変わります。
while second:は余りが0になると止まります。return abs(first)は負の入力でも正の結果を返します。
どんな場面で使う?
- 分数や比を約分する。
- 最小公倍数を求める:a * b
//gcd(a, b)。 - 数のパズル、剰余演算(余りを使う計算)、暗号の基礎。
使わなくてよいとき
- 実際のコード:標準で
math.gcdが用意されていて、最近の Python では引数をいくつでも渡せます。 - すべての公約数を求める場合:最大公約数で分かるのは、いちばん大きい公約数だけです。
サンプルコード
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))
実行結果
6
コードの解説
各ステップで、ペア(first, second)を(second, first % second)に置き換えます。余りが0になったとき、firstに残った値が最大公約数なので、48と18の最大公約数は6です。abs()関数で結果が必ず正になるようにしています。必要なステップ数は数の大きさに対してとてもゆっくりしか増えず、およそO(log n)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
余りの代わりに引き算を使う
引き算を繰り返しても同じ答えになりますが、2つの数の差が大きいと非常に遅くなります。
while first != second:
if first > second:
first -= second
else:
second -= first
while second:
first, second = second, first % second
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
- 最大公約数 2つの値の両方を割り切る最大の数を求めてください。 簡単
- 最小公倍数 両方の値で割り切れる最小の正の整数を求めてください。 簡単
- 正確な分数演算 分数の演算を行い、約分された分数を返してください。 中級