How to Find Gcd, Lcm on a Set of Numbers

How to find GCD, LCM on a set of numbers

I've used Euclid's algorithm to find the greatest common divisor of two numbers; it can be iterated to obtain the GCD of a larger set of numbers.

private static long gcd(long a, long b)
{
    while (b > 0)
    {
        long temp = b;
        b = a % b; // % is remainder
        a = temp;
    }
    return a;
}

private static long gcd(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = gcd(result, input[i]);
    return result;
}

Least common multiple is a little trickier, but probably the best approach is reduction by the GCD, which can be similarly iterated:

private static long lcm(long a, long b)
{
    return a * (b / gcd(a, b));
}

private static long lcm(long[] input)
{
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
    return result;
}

What is the most efficient way to calculate the least common multiple of two integers?

The least common multiple (lcm) of a and b is their product divided by their greatest common divisor (gcd) ( i.e. lcm(a, b) = ab/gcd(a,b)).

So, the question becomes, how to find the gcd? The Euclidean algorithm is generally how the gcd is computed. The direct implementation of the classic algorithm is efficient, but there are variations that take advantage of binary arithmetic to do a little better. See Knuth's "The Art of Computer Programming" Volume 2, "Seminumerical Algorithms" § 4.5.2.

Least common multiple for 3 or more numbers

You can compute the LCM of more than two numbers by iteratively computing the LCM of two numbers, i.e.

lcm(a,b,c) = lcm(a,lcm(b,c))

GCD and LCM relation

The analogous formulas to

LCM(a, b) = (a x b) / GCD(a,b) or GCD(a,b) = (a x b) / LCM(a, b) 

with three variables are simply not valid, as your example with (3, 12, 10) shows readily.

The product of these three numbers is 360. The GCD is 1. The LCM is 60.

How to get GCD and LCM of a range of numbers efficiently?

As mentioned by Chris J this SO question provides the algorithm. Here is a python version of the answer that uses the reduce built-in and the fractions module that has been around since version 2.6.

import fractions

def gcd(*values):
    return reduce(fractions.gcd, values)

To find lcm without gcd algorithm-regarding

while(1) : 
    if (i % small == 0): 
        return i 
    i += lar 

This is weird and un-pythonic. Just do

while i % small != 0:
   i += lar
return i

i += lar is (for the purpose of this example) equivallent to i = i + lar.

If you are asking for the algorithmic logic, then think about it. You are trying to find the least common multiple. So you start by checking if the smaller number evenly divides the larger one (in other words, is the larger number already the least common multiple). If not, you accumulate multiples of the larger number until you find the one that the smaller number does evenly divide, and return it.

BTW, if we are already making this code more pythonic, the function name should be find_lcm.

---

Related Topics