最大公約数

最大公約数

最大公約数 (greatest common divisor)

 2 数 a, b の共通の約数のうち、最大数を 最大公約数 とよびます。標準ライブラリの mathモジュールと代数計算用パッケージ SymPy に最大公約数を求める関数が用意されています。

math.gcd()

 math.gcd() は 2 つの引数 a, b を受け取って 最大公約数 を返します。

# リストGC01-1

# mathをインポート
import math

# 10と15の最大公約数
x = math.gcd(10, 15)

print(x)
5

 math.gcd() には 2 つの引数しか渡せませんが、集約関数 functools.reduce() を使うと、可変引数を受け取って最大公約数を返す関数を定義できます。

# リストGC01-2

# functoolsをインポート
import functools

# 可変引数を受け取って最大公約数を返す関数
def gcd_2(*vals):
    return functools.reduce(math.gcd, vals)

 gcd_2() を使って (10, 15, 20) の最大公約数を求めてみます。

# リストGC01-3

# (10,15,20)の最大公約数
x = gcd_2(10, 15, 20)

print(x)
5

 

SymPyによる最大公約数の計算

sympy.gcd(a, b) は a と b の 最大公約数 を返します。

# リストGC02-1

import sympy

# 16と24の最大公約数
x = sympy.gcd(16, 24)

print(x)
8

 a, b には数式を渡すこともできます。

# リストGC02-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 の最大公約数をとります。

# リストGC03

# 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