最小公倍数を求めるやつ

ある2つの数x,yの最小公倍数は、それらをかけ合わせたものをそれらの最大公約数で割るとイケます。すなわち、x,yの最大公約数、最小公倍数をそれぞれgcd(x, y), lcm(x, y)とすると、

x*y = gcd(x, y) * lcm(x, y)

が成り立ちます。

最大公約数はこの回でやったのでこいつを利用するだけですね。

or3.hatenablog.com

# lcm

def gcd(x, y):
    if x<y:
        gcd(y,x)
    r = y
    while x%y is not 0:
        r = x%y
        x, y = y, r
    return r


def lcm(x, y):
    if(x<y):
        lcm(y, x)
    if x%y==0:
        return x
    return (x*y)/gcd(x, y)

print(lcm(927,2864))