Lowest Common Multiple (LCM)

Question: The least common multiple (LCM), also known as the lowest common multiple, of two or more non-zero integers is the smallest positive integer that is a integer multiple of both the numbers. Provide an efficient algorithm to compute LCM of two numbers.


We have an efficient algorithm to compute GCD, we will use a simple mathematical formula to find the LCM using GCD algorithm.

Time Complexity: O(n)

/* mod method */

int gcd(int n1, int n2)

{

    int temp;

    while (n2 != 0) {

        temp = n2;

        n2 = n1 % n2;

        n1 = temp;

    }

    return n1;

}

int lcm(int n1, int n2)

{

    return ((n1 * n2) / gcd(n1, n2));

}