【Python】関数を使わずに最大公約数を求める方法

この記事では、Pythonを使って最大公約数を求める3つの方法を紹介します。

ユークリッドの互除法や素因数分解、総当たりでの方法を通じて、最大公約数を求める手法を理解しましょう。

目次から探す

最大公約数を求める方法

方法1: ユークリッドの互除法を用いた最大公約数の求め方

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

この方法は、2つの整数を比較して、大きい方を小さい方で割った余りを求め、その余りと小さい方の数を使って同じ操作を繰り返すことで最大公約数を求めます。

以下に、ユークリッドの互除法を用いて最大公約数を求めるPythonのサンプルコードを示します。

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

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

方法2: 素因数分解を用いた最大公約数の求め方

素因数分解は、数を素数の積に分解する方法です。

2つの整数の素因数分解を行い、共通する素因数を掛け合わせることで最大公約数を求めることができます。

以下に、素因数分解を用いて最大公約数を求めるPythonのサンプルコードを示します。

# 素因数分解する関数
def factorization(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

# 最大公約数を求める関数
def greatest_common_divisor(a, b):
    factors_a = factorization(a)
    factors_b = factorization(b)
    gcd = 1
    for factor in factors_a:
        if factor in factors_b:
            gcd *= factor
            factors_b.remove(factor)
    return gcd

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

方法3: 総当たりで最大公約数を求める方法

総当たりで最大公約数を求める方法は、2つの整数のうち小さい方から1ずつ減らしながら、両方の数を割り切れる最大の数を見つける方法です。

この方法は単純ですが、大きな数に対しては効率が悪いため、一般的にはあまり使用されません。

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

def brute_force_gcd(a, b):
    gcd = 1
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            gcd = i
    return gcd

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

終わりに

最大公約数を求める方法にはさまざまなアプローチがあります。

ユークリッドの互除法や素因数分解を用いる方法は効率的で一般的ですが、総当たりで求める方法も理解しやすく実装しやすい特徴があります。

適切な方法を選択して、問題に応じて最大公約数を求めることが重要です。

目次から探す