Pythonで最大公約数と最小公倍数を算出・取得

Pythonで最大公約数と最小公倍数を算出・取得する方法について、

2つの整数の最大公約数・最小公倍数 3つ以上の整数の最大公約数、最小公倍数

をそれぞれ説明します。

2つの整数の最大公約数・最小公倍数

最大公約数 バージョン3.5以降はmathモジュールにgcd()関数があります。

math.gcd() --- 数学関数 — Python 3.7.3 ドキュメント

gcdは「greatest common divisor」の頭文字。 引数として二つの整数を渡すと最大公約数を返します。

import math

a = 6
b = 4

print(math.gcd(a, b))
# 2

以前のバージョン(3.4以前)ではmathモジュールではなくfractionsモジュールにgcd()関数があるので気をつけてください。

fractions.gcd() --- 有理数 — Python 3.7.3 ドキュメント

最小公倍数 最小公倍数lcm( least common multiple)を返す関数は用意されていないが、

lcm(a, b) = a * b / gcd(a, b)

なので、gcd()関数を使って簡単に算出できます。

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(a, b))
# 12

/を使うと結果が小数floatになるため、小数点以下を切り捨て整数の除算結果を返す//(整数除算)を使っています。

3つ以上の整数の最大公約数、最小公倍数

3つ以上の複数の整数の最大公約数・最小公倍数を求める場合、特に複雑なアルゴリズムは必要なく、2つずつ再帰的に演算していけば問題ありません。 高階関数reduce()を使って複数の値に対して順番に最大公約数・最小公倍数を計算します。

可変長引数で任意の個数の値を受け取る関数 リスト(配列)で値を受け取る関数

が考えられます。 可変長引数を使う場合は*をつけることでリスト(配列)を渡すこともできます。 お好みで。 最大公約数

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

print(gcd(27, 18, 9))
# 9

print(gcd(27, 18, 9, 3))
# 3

print(gcd([27, 18, 9, 3]))
# [27, 18, 9, 3]

print(gcd(*[27, 18, 9, 3]))
# 3

print(gcd_list([27, 18, 9, 3]))
# 3

# print(gcd_list(27, 18, 9, 3))
# TypeError: gcd_list() takes 1 positional argument but 4 were given

繰り返しになるが、以前のバージョン(3.4以前)ではmathモジュールではなくfractionモジュールにgcd()関数があるので気をつけてください。 最小公倍数

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

print(lcm(27, 18, 9, 3))
# 54

print(lcm(27, 9, 3))
# 27

print(lcm(*[27, 9, 3]))
# 27

print(lcm_list([27, 9, 3]))
# 27
Last Updated: 6/26/2019, 10:34:03 PM