lcm (Least Common Multiple)

Tags: [math], [lcm], [gcd]

Link: https://zh.wikipedia.org/wiki/最小公倍數

Given two integers a and b, calculate the Least Common Multiple.

Solution: Using gcd to calculate the lcm

def get_lcm(a, b):
    if not a:
        return b
    if not b:
        return a

    a = abs(a)
    b = abs(b)

    gcd = get_gcd(a, b)
    lcm = a * b / gcd
    return lcm

def get_gcd(a, b):
    r = a % b
    # base case
    if r == 0:
        return b
    return get_gcd(b, r)

if __name__ == '__main__':
    print 'Program is working'

    # a = -10
    # b = 15

    a = 0
    b = 0

    lcm = get_lcm(a, b)
    print lcm

    print 'Program is end'

Revelation:

• lcm = |a*b| / gcd(a, b), reference: https://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B8

Note:

• The 'Least Common Multiple' must be a positive integer (0 is not lcm). 几个数共有的倍数叫做这几个数的公倍数，其中除0以外最小的一个公倍数，叫做这几个数的最小公倍数, reference: http://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0
• Time complexity = O(lgb).