Python で GCD 操作を実装する

1. Python で再帰を使用して GCD のコードを実装する
2. Python で for ループを使用して最大公約数のコードを実装する
3. Python でユークリッドアルゴリズムを使用して最大公約数のコードを実装する
4. Python で math.gcd() 関数を使用して最大公約数を計算する

2つの値の最大公約数（HCF）とも呼ばれる最大公約数（GCD）は、指定された両方の数値を除算する最大数です。最大公約数は、Python でも計算および実装できます。

このチュートリアルでは、Python で最大公約数のコードを実装するためのさまざまな方法を示します。

Python で再帰を使用して GCD のコードを実装する

関数定義ブロックでそれ自体を呼び出す関数は、再帰と呼ばれます。再帰を使用して、2つの数値の GCD を計算する関数を作成できます。このプロセスは、コードの長さを短縮するのに非常に役立ち、不要な関数呼び出しを最小限に抑えるのに役立ちます。

次のコードは、再帰を使用して、Python で最大公約数のコードを実装します。

def gcd1(x, y):
    if y == 0:
        return x
    else:
        return gcd1(y, x % y)


x = 72
b = 60

print("The gcd is : ", end="")
print(gcd1(72, 60))

上記のプログラムは次の結果をもたらします。

出力：

The gcd is : 12

Python で for ループを使用して最大公約数のコードを実装する

単純な for ループと if-else ステートメントは、この記事の他のメソッドと同じタスクを実行するのに役立ちます。

次のコードは、for ループを使用して、Python で最大公約数のコードを実装します。

def gcd2(a, b):

    if a > b:
        small = b
    else:
        small = a
    for i in range(1, small + 1):
        if (a % i == 0) and (b % i == 0):
            gcd = i

    return gcd


a = 72
b = 60

print("The gcd is : ", end="")
print(gcd2(72, 60))

上記のコードは次の結果をもたらします。

出力：

The gcd is : 12

Python でユークリッドアルゴリズムを使用して最大公約数のコードを実装する

ユークリッドアルゴリズムは、2つの数値の最大公約数をすばやく計算できるもう 1つの手法です。

ユークリッドアルゴリズムは、2つの主要な事実に基づいて定義されています。

• 小さい数値から大きい数値を引いても、GCD に変化はありません。したがって、2つの数値のうち大きい方の値を継続的に減算すると、最終的に GCD がわかります。
• 小さい方の数値を除算すると、ここで減算する代わりに、余り 0 が検出されるとアルゴリズムが自動的に停止します。

以下のプログラムは、ユークリッドアルゴリズムを使用して、Python で最大公約数のコードを実装します。

def gcd3(p, q):

    while q:
        p, q = q, p % q

    return p


p = 72
q = 60

print("The gcd is : ", end="")
print(gcd3(72, 60))

コードは次の結果を提供します。

出力：

The gcd is : 12

Python で math.gcd() 関数を使用して最大公約数を計算する

これで、ユーザー定義関数を作成する代わりに、事前定義された math.gcd() 関数を使用して、2つの数値の GCD を計算できます。gcd() 関数を使用するには、math モジュールを Python コードにインポートする必要があります。

次のコードは、math.gcd() 関数を使用して、Python で最大公約数を計算します。

import math

a = math.gcd(72, 60)
print(a)

上記のプログラムは次の結果を提供します。

出力：

12

Python 3.5 以降では、gcd 関数は math モジュールに含まれています。以前の Python バージョンでは、gcd 関数は fractions モジュールに含まれていました。ただし、Python 3.5 以降、非推奨になりました。