Least Common Multiple

In mathematics, the Least Common Multiple (LCM), also known as smallest common multiple, of two postive integers \(a\) and \(b\) is the smallest positive integer that is divisible by both \(a\) and \(b\). 1 Denoted by: \(\begin{equation} \operatorname{lcm}(x,y) \end{equation}\). 2

Implementation

\(\operatorname{lcm}(x,y)\) can be detrieved from \(gcd(a, b)\), recall that Euclidean algorithm is one of the most effiecient methods for computing the Greatest Common Divisor(GCD) of two integers.

\[\begin{equation} \operatorname{lcm}(a,b) = \frac{\lvert ab \rvert}{\gcd(a,b)} \end{equation}\]

def lcm(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // gcd(a, b)

LCM of a List of Integers

To compute the LCM of a list integers, we iterate the array:

Let first element as initial lcm, denoted \(result\);
Calculate the LCM of \(result\) and next element, and repeat till end.

def lcm_of_list(arr: list[int] -> int):
    if not arr: raise ValueError("Array must contain at least one element")
    result = arr[0]
    for ele in arr[1:]:
        result = lcm(result, ele)
    return result

Practice

References

Weisstein, Eric W. “Least Common Multiple”. mathworld.wolfram.com. Retrieved 2020-08-30.
↗ Least Common Multiple - Wikipedia