paiza ユークリッドの互除法メニュー 最小公倍数Python解説

スポンサーリンク

最小公倍数

最大公約数(以後 gcd)と対になる値として、最小公倍数(以後 lcm)があります。
一般的に直接 lcm を求めるよりも、gcd を求めてから計算によって lcm を求める方が簡単とされています。
2 つの整数 A , B の lcm(A,B) は、lcm(A,B) = A×B/gcd(A,B) で求めることができます。
2 つの整数 A , B が与えられるので、lcm (A,B) を求めてください。

paiza「最小公倍数」

問題文の通り、ユークリッドの互除法を使いA,Bの最大公約数を求めたら、A * Bを最大公約数で割り、最小公倍数を求めたいと思います。

a, b = map(int, input().split())

def gcd(a, b):
    if b == 0:
        return a 
    return gcd(b, a % b)
    
print(a * b // gcd(a, b))

まず、ユークリッドの互除法を関数で定義します。入力から受け取ったa, bの値の最大公約数を求め、最後にa * b // gcd(a, b)を計算すれば最小公倍数を求めることができます。