user339108 - 5 months ago 7x
Java Question

# How to find GCF, LCM on a set of numbers

What would be the easiest way to calculate Greatest Common Factor and Least Common Multiple on a set of numbers? What math functions can be used to find this information?

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;
}
``````
Source (Stackoverflow)