最大公約数
2 数 a, b の共通の約数のうち、最大数を 最大公約数 (gcd:greatest common divisor) とよびます。たとえば 12 の約数は
1, 2, 3, 4, 6, 12
であり、18 の約数を並べると
1, 2, 3, 6, 9, 18
なので、12 と 18 の共通の約数は
1, 2, 3, 6
であり、その中の最大数 (最大公約数) は 6 となります。
math.gcd()
math.gcd() は 2 つの引数 a, b を受け取って最大公約数を返します (Python 3.9 以降では、3 つ以上の引数を受け取れるようになったようです)。
# PYTHON_GCD
# In[1]
import math
# 10と15の最大公約数
x = math.gcd(10, 15)
print(x)
# 5
math.gcd() には 2 つの引数しか渡せませんが、集約関数 functools.reduce() を使うと、可変引数を受け取って最大公約数を返す関数を定義できます。
# In[2]
# functoolsをインポート
import functools
# 可変引数を受け取って最大公約数を返す関数
def gcd_2(*vals):
return functools.reduce(math.gcd, vals)
gcd_2() を使って (10, 15, 20) の最大公約数を求めてみます。
# In[3]
# (10,15,20)の最大公約数
x = gcd_2(10, 15, 20)
print(x)
# 5
numpy.gcd()
numpy.gcd(x1, x2) は x1 と x2 の最大公約数を返します。
# NUMPY_GCD
# In[1]
import numpy as np
# 450と7182の最大公約数
gcd = np.gcd(450, 7182)
print(gcd)
# 18
x1, x2 に配列を渡すこともできます。このとき、x1 と x2 のサイズが等しければ、同じインデックスの要素同士で最大公約数を計算します。
# In[2]
x1 = [10, 12, 15]
x2 = [20, 30, 90]
# 10と20,12と30,15と90の最大公約数
gcd = np.gcd(x1, x2)
print(gcd)
# [10 6 15]
x1 と x2 のサイズが異なる場合、ブロードキャストして最大公約数を計算します。
# In[3]
x2 = [12, 15, 40]
# 100と12,100と15,100と40の最大公約数
gcd = np.gcd(100, x2)
print(gcd)
# [4 5 20]
3 数以上の最大公約数を求めるときには、reduce() メソッドで集約します。
# In[4]
x = np.array([8, 12, 40])
# 8,12,40の最大公約数
gcd = np.gcd.reduce(x)
print(gcd)
# 4
sympy.gcd()
sympy.gcd(a, b) は a と b の 最大公約数 を返します。
# SYMPY_GCD
# In[1]
import sympy
# 16と24の最大公約数
x = sympy.gcd(16, 24)
print(x)
# 8
a, b には数式を渡すこともできます。
# In[2]
# 記号xを定義
sympy.var('x')
# 数式f,gを定義
f = 3*x**2 + 7*x + 2
g = x**2 + 7*x + 10
# fとgの最大公約数
x = sympy.gcd(f, g)
print(x)
# x + 2
sympy.gcd() には引数を 3 個以上渡せないので、3 つの数 a, b, c の最大公約数を求めたい場合は、gcd(a, b) と c の最大公約数をとります。
# In[3]
# 3数の最大公約数を求める関数
def triple_gcd(a, b, c):
from sympy import gcd
return gcd(gcd(a,b), c)
# 24,48,60の最大公約数
x = triple_gcd(24, 48, 60)
print(x)
# 12
【GPT解説】最大公約数を計算するアルゴリズム
最大公約数(Greatest Common Divisor、GCD)は、2つ以上の整数の中で共通の約数のうち最大のものです。最大公約数は整数の間の共通の要因を見つけるために使用され、数学や計算機科学のさまざまな分野で重要な役割を果たしています。具体的な整数の最大公約数を求める際には、以下の方法が一般的に使用されます。
素因数分解を用いる方法:与えられた2つの整数をそれぞれ素因数分解し、共通する素因数のうち、指数が最小のものを掛け合わせます。これにより、最大公約数が得られます。ただし、この方法は素因数分解が必要であり、大きな整数の場合には計算が複雑になることがあります。
ユークリッドの互除法を用いる方法:ユークリッドの互除法は、2つの整数の最大公約数を求めるための効率的なアルゴリズムです。互除法では、与えられた2つの整数のうち大きな方を小さい方で割り、その余りを新しい2つの数として使います。この操作を繰り返し、余りが0になるまで続けます。最終的に、最後に割った数が最大公約数となります。以下はユークリッドの互除法を用いて最大公約数を求める例です:
gcd(a, b) = gcd(b, a % b)
ここで、a と b は整数で、% は剰余演算子です。この操作を再帰的に行い、余りが0になったときの b が最大公約数です。最大公約数は、整数の分数を簡約する際や、一様分布の周期性を調べる際など、さまざまな数学的な問題に関連して使用されます。また、アルゴリズムやデータ構造の最適化など、計算機科学の分野でも重要な役割を果たしています。