Single loop: Least Common Multiple (LCM)

Problem: Compute LCM (Least Common Multiple) of 2 positive integers.

Example:


LCM(5,7) = 35
LCM(10,8) = 40
LCM(45,30) = 90

Hint: LCM(n,m) * GCD(n,m) = n * m

Solution in Python:


def lcm(n, m):
    """
    Author: Mayur P Srivastava

    """

    if n < m:
        gcd = gcd2(m, n)
    else:
        gcd = gcd2(n, m)

    result = n * m // gcd
    print "LCM(%d,%d) = %d" % (n, m, result)

    
def gcd2(n, m):
    while m != 0:
        r = n % m
        n = m
        m = r
    return n


Concepts learned: Single loop.