【Python】ユークリッドの互除法を使って最大公約数を求める方法

この記事では、ユークリッドの互除法を使って、2つの数や複数の数の最大公約数を求める方法を学ぶことができます。

ユークリッドの互除法は、簡単な手順で最大公約数を見つけることができる便利なアルゴリズムです。

目次から探す

ユークリッドの互除法とは

ユークリッドの互除法は、2つの整数の最大公約数を求めるためのアルゴリズムです。

この方法は古代ギリシャの数学者であるユークリッドによって発見されました。

ユークリッドの互除法は、非常に効率的であり、現代でも広く使われています。

ユークリッドの互除法の基本

ユークリッドの互除法の基本的な考え方は、2つの整数aとbについて、aをbで割った余りをrとすると、aとbの最大公約数は、bとrの最大公約数と等しいという性質に基づいています。

この性質を繰り返し適用することで、最終的に最大公約数を求めることができます。

ユークリッドの互除法の手順

  1. 2つの整数aとbを用意する。
  2. aをbで割った余りをrとする。
  3. もしrが0であれば、bが最大公約数となる。
  4. もしrが0でなければ、aにbの値を代入し、bにrの値を代入して、手順2に戻る。

ユークリッドの互除法は、このように簡単な手順で最大公約数を求めることができます。次に、実際にPythonを使ってユークリッドの互除法を実装してみましょう。

ユークリッドの互除法を使った最大公約数の求め方

2つの数の最大公約数を求める方法

ユークリッドの互除法を使って2つの数の最大公約数を求める方法は、以下の手順に従います。

  1. まず、2つの数をaとbとします。aをbで割った余りをrとします。
  2. 次に、bをrで割った余りを新たなrとします。
  3. この操作を繰り返し、余りが0になった時の除数が最大公約数となります。

以下に、Pythonでこの手法を用いて2つの数の最大公約数を求めるサンプルコードを示します。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

num1 = 24
num2 = 36
result = gcd(num1, num2)
print(f"{num1}と{num2}の最大公約数は{result}です。")
24と36の最大公約数は12です。

このサンプルコードでは、gcd関数を定義し、2つの数を引数として受け取ってユークリッドの互除法を用いて最大公約数を求めています。

複数の数の最大公約数を求める方法

複数の数の最大公約数を求める場合も、ユークリッドの互除法を使うことができます。

以下に、Pythonで複数の数の最大公約数を求めるサンプルコードを示します。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcd_multiple(numbers):
    result = numbers[0]
    for num in numbers[1:]:
        result = gcd(result, num)
    return result

numbers = [24, 36, 48, 60]
result = gcd_multiple(numbers)
print(f"{numbers}の最大公約数は{result}です。")
[24, 36, 48, 60]の最大公約数は12です。

このサンプルコードでは、gcd_multiple関数を新たに定義し、リストとして複数の数を受け取り、それらの数の最大公約数を求めています。

これらのサンプルコードを実行することで、ユークリッドの互除法を使って2つまたは複数の数の最大公約数を求める方法を確認することができます。

目次から探す