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

2024-02-132024-07-21

この記事では、Pythonを使って関数を使わずに2つの数の最大公約数を求める方法について学びます。

最大公約数とは何か、その求め方として「ユークリッドの互除法」と「素因数分解」の2つの方法を紹介し、それぞれのアルゴリズムを具体的な例とともに解説します。

また、これらの方法の効率性や実行速度の比較も行い、関数を使わないメリットとデメリットについても考察します。

目次から探す

最大公約数とは

最大公約数の定義

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

公約数とは、ある整数を割り切ることができる数のことです。

例えば、12と18の公約数は1, 2, 3, 6ですが、その中で最も大きい6が最大公約数となります。

最大公約数(GCD: Greatest Common Divisor)とは

最大公約数は英語で Greatest Common Divisor と呼ばれ、略してGCDと表記されることが多いです。

GCDは数学やコンピュータサイエンスの分野で頻繁に使用される概念であり、特に数論やアルゴリズムの設計において重要な役割を果たします。

数学的な背景と基本概念

最大公約数の概念は、数の分解や因数分解に基づいています。

2つの数の最大公約数を求めるためには、それぞれの数を素因数分解し、共通する素因数の積を求める方法があります。

例えば、48と18の最大公約数を求める場合、以下のように素因数分解を行います。

48 = 2^4 * 3
18 = 2 * 3^2

共通する素因数は2と3であり、それぞれの最小の指数を取ると、2^1 * 3^1 = 6が最大公約数となります。

最大公約数の求め方

最大公約数を求める方法はいくつかありますが、代表的なものとして「ユークリッドの互除法」と「素因数分解」があります。

以下では、それぞれの方法について詳しく説明します。

ユークリッドの互除法

ユークリッドの互除法は、古代ギリシャの数学者ユークリッドによって考案されたアルゴリズムで、2つの整数の最大公約数を効率的に求めることができます。

この方法は、以下の手順で行います。

2つの整数aとbを用意します(a > bとします)。
aをbで割り、その余りをrとします。
rが0でない場合、aをbに、bをrに置き換えて手順2に戻ります。
rが0になった時点で、bが最大公約数となります。

具体例として、48と18の最大公約数を求める場合を考えます。

48を18で割ると、余りは12です。
18を12で割ると、余りは6です。
12を6で割ると、余りは0です。

したがって、48と18の最大公約数は6となります。

素因数分解

素因数分解を用いて最大公約数を求める方法もあります。

この方法では、各整数を素因数に分解し、共通する素因数の積を求めます。

具体的な手順は以下の通りです。

2つの整数を素因数分解します。
共通する素因数を見つけます。
共通する素因数の最小の指数を取ります。
それらの積を求めます。

例えば、48と18の最大公約数を求める場合、以下のように素因数分解を行います。

48 = 2^4 * 3
18 = 2 * 3^2

共通する素因数は2と3であり、それぞれの最小の指数を取ると、2^1 * 3^1 = 6が最大公約数となります。

以上のように、最大公約数を求める方法にはユークリッドの互除法と素因数分解があります。

それぞれの方法には利点と欠点があり、具体的な状況に応じて使い分けることが重要です。

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

ユークリッドの互除法を用いた方法

ユークリッドの互除法のアルゴリズム

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

この方法は、以下の手順で行います。

2つの整数 (a) と (b) を用意します(ここで (a > b) とします)。
(a) を (b) で割り、その余りを (r) とします。
(a) を (b) に、(b) を (r) に置き換えます。
(r) が 0 になるまで2と3を繰り返します。
最後に (b) が最大公約数となります。

アルゴリズムの説明

ユークリッドの互除法は、繰り返し割り算を行うことで最大公約数を求める方法です。

割り算の余りが0になるまで計算を続けることで、最終的に最大公約数が得られます。

この方法は非常に効率的で、大きな数でも短時間で計算が可能です。

具体例を用いた解説

例えば、48と18の最大公約数を求める場合を考えます。

48 ÷ 18 = 2 余り 12
18 ÷ 12 = 1 余り 6
12 ÷ 6 = 2 余り 0

この場合、余りが0になった時の除数(6)が最大公約数となります。

Pythonでの実装

whileループを用いた実装

Pythonでユークリッドの互除法を用いて最大公約数を求める方法を、関数を使わずに実装してみましょう。

具体的なコード例

# 2つの整数を定義
a = 48
b = 18
# ユークリッドの互除法を用いて最大公約数を求める
while b != 0:
    a, b = b, a % b
# 結果を表示
print("最大公約数は", a)

このコードでは、whileループを用いてユークリッドの互除法を実装しています。

ループが終了した時点で、変数 a に最大公約数が格納されます。

素因数分解を用いた方法

素因数分解のアルゴリズム

素因数分解を用いて最大公約数を求める方法もあります。

この方法は、以下の手順で行います。

2つの整数 (a) と (b) を素因数分解します。
共通の素因数を見つけ、その指数の最小値を取ります。
共通の素因数の積が最大公約数となります。

アルゴリズムの説明

素因数分解を用いる方法は、2つの整数をそれぞれ素因数に分解し、共通の素因数を見つけることで最大公約数を求めます。

この方法は、特に小さな数に対して有効です。

具体例を用いた解説

例えば、48と18の最大公約数を素因数分解を用いて求める場合を考えます。

48の素因数分解:
18の素因数分解:
共通の素因数は2と3で、それぞれの指数の最小値は1と1です。
よって、最大公約数はとなります。

Pythonでの実装

forループを用いた実装

Pythonで素因数分解を用いて最大公約数を求める方法を、関数を使わずに実装してみましょう。

具体的なコード例

# 2つの整数を定義
a = 48
b = 18
# 素因数分解を行う関数を定義
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
# 2つの整数の素因数分解を行う
factors_a = prime_factors(a)
factors_b = prime_factors(b)
# 共通の素因数を見つける
common_factors = set(factors_a) & set(factors_b)
# 最大公約数を計算
gcd = 1
for factor in common_factors:
    gcd *= factor ** min(factors_a.count(factor), factors_b.count(factor))
# 結果を表示
print("最大公約数は", gcd)

このコードでは、素因数分解を行うための関数 prime_factors を定義し、2つの整数の素因数分解を行っています。

その後、共通の素因数を見つけ、最大公約数を計算しています。

実装の比較と考察

ユークリッドの互除法 vs 素因数分解

最大公約数を求める方法として、ユークリッドの互除法と素因数分解の2つの方法があります。

これらの方法にはそれぞれの特徴と利点があります。

ユークリッドの互除法

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

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

計算量が少なく、特に大きな数に対しても高速に動作します。

素因数分解

素因数分解は、2つの整数をそれぞれ素因数に分解し、共通の素因数の積を求めることで最大公約数を求める方法です。

この方法は、数の性質を深く理解するのに役立ちますが、特に大きな数に対しては計算量が多くなりがちです。

アルゴリズムの効率性

アルゴリズムの効率性を評価する際には、計算量や実行時間が重要な指標となります。

ユークリッドの互除法の効率性

ユークリッドの互除法は、計算量がO(log(min(a, b)))であり、非常に効率的です。

これは、2つの数のうち小さい方の対数に比例して計算時間が増加することを意味します。

特に大きな数に対しても高速に動作するため、実用的な場面でよく使用されます。

素因数分解の効率性

素因数分解の計算量は、数の大きさに対して指数関数的に増加することがあります。

特に大きな数に対しては、素因数分解の計算が非常に時間がかかることがあります。

そのため、実用的な場面ではあまり使用されないことが多いです。

実行速度の比較

実行速度の比較を行うために、Pythonで実際にコードを実行してみましょう。

以下に、ユークリッドの互除法と素因数分解を用いた最大公約数の計算を行うコードを示します。

ユークリッドの互除法の実行速度

import time
# ユークリッドの互除法
def gcd_euclidean(a, b):
    while b != 0:
        a, b = b, a % b
    return a
# 実行時間の計測
start_time = time.time()
print(gcd_euclidean(123456, 789012))
end_time = time.time()
print("ユークリッドの互除法の実行時間: ", end_time - start_time)

素因数分解の実行速度

import time
# 素因数分解を用いた最大公約数の計算
def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
def gcd_prime_factors(a, b):
    factors_a = prime_factors(a)
    factors_b = prime_factors(b)
    common_factors = set(factors_a) & set(factors_b)
    gcd = 1
    for factor in common_factors:
        gcd *= factor
    return gcd
# 実行時間の計測
start_time = time.time()
print(gcd_prime_factors(123456, 789012))
end_time = time.time()
print("素因数分解の実行時間: ", end_time - start_time)