Pythonで学ぶユークリッドの互除法：最大公約数（GCD）を求める基本プログラム

はじめに

この記事では、以下の問題に対する解決策について詳しく解説していきます。

問題の概要

問題文： 2つの数値が与えられたとき、その最大公約数（GCD）を計算して表示します。

GCD（Greatest Common Divisor：最大公約数）とは、2つの数をどちらも余りなく割り切ることができる最大の整数のことです。ここではユークリッドの互除法を用いてGCDを計算します。この手法では、数値同士の割り算を繰り返し行い、余りが0になった時点で計算を終了します。

ユークリッドの互除法の仕組み

ユークリッドの互除法は、次のような手順で動作します。

1. 2つの数 a と b を用意します。
2. a が 0 の場合、b が最大公約数となります。
3. そうでなければ、a を b % a（b を a で割った余り）に置き換え、再帰的に処理を繰り返します。

この方法により、大きな数同士でも少ない計算回数で効率的に最大公約数を求めることができます。

実装例

# euclid algorithm for calculation of greatest common divisor
def gcd(a, b):
    if a == 0 :
        return b
    return gcd(b%a, a)
a = 11
b = 15
print("gcd of ", a , "&" , b, " is = ", gcd(a, b))

出力結果

gcd of 11 & 15 is = 1

上記のコードでは、すべての変数がローカルスコープ内で宣言されており、その参照関係は図のようになっています。11と15は互いに素であるため、最大公約数は1となることが確認できます。

まとめ

この記事では、基本的なユークリッドの互除法を実装したPythonプログラムの作成方法について学びました。このアルゴリズムは再帰的な構造を持ち、シンプルでありながら非常に効率的に最大公約数を求められるのが特徴です。暗号技術や分数の約分など、さまざまな場面で応用される重要なアルゴリズムなので、ぜひマスターしておきましょう。