def gcd (a, b):
    for i in range(min(a, b), 0, -1):
        if a%i == 0 and b%i == 0:
            return i

def gcd_euclides_1 (a, b):
    while a !=b:
        if a > b:
            a = a -b
        else:
            b = b -a
    return a

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

def lcm (a, b):
    return (a*b)//gcd(a, b)