How to find GCD, LCM on a set of numbers

Question

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

Answer 1

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; } 

Answer 2

There is an Euclid's algorithm for GCD,

public int GCF(int a, int b) {     if (b == 0) return a;     else return (GCF (b, a % b)); } 

By the way, a and b should be greater or equal 0, and LCM = |ab| / GCF(a, b)