【Python】while文を使って最大公約数を求める方法

この記事では、2つの整数の最大公約数を求めるための方法であるユークリッドの互除法を、Pythonのwhile文を使って実装する手順を紹介します。

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

目次から探す

最大公約数とは

最大公約数とは、2つ以上の整数の中で共通の約数のうち最も大きなものを指します。

例えば、12と18の最大公約数は6です。

最大公約数は、数学的な計算やプログラミングにおいて重要な概念であり、特に整数の計算や問題解決において利用されます。

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

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

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

ユークリッドの互除法は、2つの整数aとbに対して、aをbで割った余りをrとして、aとbの代わりにbとrを新たな2つの整数として考え、再帰的に計算を行います。

この操作を繰り返すことで、最終的に余りが0になったときの除数が最大公約数となります。

ユークリッドの互除法は、2つの整数aとbに対して、aをbで割った余りをrとして、aとbの代わりにbとrを新たな2つの整数として考え、再帰的に計算を行うアルゴリズムです。

ユークリッドの互除法をwhile文を使って実装する方法

初期値の設定

ユークリッドの互除法をwhile文を使って実装する際には、最初に2つの整数の値を受け取ります。

これらの値を変数に代入し、後続の計算で使用します。

while文を使ったアルゴリズムの流れ

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

while文を使って実装する場合、以下の手順で計算を行います。

  1. 2つの整数a, bのうち、大きい方をa、小さい方をbとします。
  2. bが0になるまで以下の計算を繰り返します。 aをbで割った余りをrとします。
  3. bが0になった時点で、aには最大公約数が格納されています。

実装例

以下に、Pythonでユークリッドの互除法をwhile文を使って実装したサンプルコードを示します。

def euclidean_algorithm(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

num1 = 48
num2 = 18
result = euclidean_algorithm(num1, num2)
print(f"{num1}と{num2}の最大公約数は{result}です。")
48と18の最大公約数は6です。

このサンプルコードでは、euclidean_algorithm関数でユークリッドの互除法を実装し、最大公約数を求めています。

num1とnum2に任意の整数を代入し、関数に渡すことで最大公約数を求めることができます。

例として、48と18の最大公約数を求める場合の実行結果が表示されます。

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

while文を使って繰り返し計算を行うことで、最大公約数を求めることができます。

目次から探す