最小公倍数と最大公約数を求めるアルゴリズム

最小公倍数は最大公約数を使って簡単に求めることができるので、まず最大公約数を求める。

最大公約数

最大公約数を求める最も有名なアルゴリズムはユークリッドの互除法である。

wikipediaから引用すると、

2つの自然数a, b (a >= b)について、aのbによる剰余をrとるすと、aとbとの最大公約数はbとrとの最大公約数に等しい。この操作を剰余が0になるまで繰り返し行い、剰余が0になったときの序数がaとbとの最大公約数となる。

例: 1071と1029の最大公約数を求める。 * 1071を1029で割った余りは42 * 1029を42で割った余りは21 * 42を21で割った余りは0 よって、1071と1029の最大公約数は21である。

これをPythonで実装すると

nums = list(map(int, input().split()))
a, b = max(nums), min(nums)

def GCD(a, b):
    while a % b != 0:
        r = a % b
        a, b = b, r
    return b

print("The GCD of {} and {} is {}.".format(a, b, GCD(a, b)))

最小公倍数

最小公倍数は で求めることができる。 Pythonで書くと

def LCM(a, b):
    return int((a * b) / GCM(a, b))

print("The LCM of {} and {} is {}.".format(a, b, LCM(a, b)))