最大公約数

当サイトではアフィリエイトプログラムを利用して商品を紹介しています。

最大公約数

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

コメント

  1. あとりえこばと より:

    【AI連載小説】科学とコードの交差点(34)「拡張ユークリッドの互除法」
     
    深夜のキャンパス内、Pythonサークルの部室に六郷開誠と刑部明信が集まり、最大公約数(GCD)を計算するアルゴリズムについて情熱的に語り合っていた。部屋の雰囲気は、コードの光に照らされながらも静謐であり、数学的な探求心が空気を支配していた。開誠が口火を切った。
    「GCDの計算にはいくつかのアルゴリズムがあるが、どれが一番良いと思う?」
    明信は考え深く答えた。
    「確かにユークリッドの互除法はシンプルで広く使われているけれど、大きな数になると効率に欠けることがあるよね」
    開誠は頷きながら続けた。
    「そうだな。特に大きな素数同士のGCDを求めるとなると、効率が問題になる。その点で、拡張ユークリッドの互除法が強力だ」
    「それはどうしてだ?」
    開誠は理路整然と説明した。
    「拡張ユークリッドの互除法は、最大公約数を求めるだけでなく、一次不定方程式 ax + by = gcd(a, b) の解も求めることができる。このアルゴリズムは、逆元やモジュラー方程式の解決にも利用され、数学的な応用が広がっている」
    明信が感心しながら続けた。
    「なるほど、一石二鳥だね。確かに大規模な計算にも適していそうだ」
    「それに、Pythonなどのプログラミング言語での実装も簡単だ。理論と計算の融合、これが最大公約数計算における理想的なアプローチだと思う」