# 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;
}
``````
-
Another neat solution for GCD is at stackoverflow.com/a/4009247/218198 – mustafailkersarac Mar 13 '14 at 14:56
Is there a faster approach in terms of complexity? – HappyCoder Jan 2 '15 at 11:35
@binaryBaBa, faster than linear in the number of integers would be impossible since you'd have to skip examining some. As for the GCD itself, binary GCD may be faster for arbitrary-precision numbers since it shifts instead of dividing. – Jeffrey Hantin Jan 5 '15 at 3:27
See also Lehmer's GCD which avoids division when the quotient would be small. I don't know that either of these would improve the asymptotic worst case bound, though. – Jeffrey Hantin Jan 5 '15 at 3:36
@Jeffrey Hantin Nonsense. There are often less-than-linear ways to determine divisors, based on the properties of the number under examination, which do indeed skip some integers. Example: if the number is odd, one can bypass even multiples of even numbers. Etc. There are many such shortcuts. – Lonny Eachus Feb 1 at 9:00

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)`

-

There are no build in function for it. You can find the GCD of two numbers using Euclid's algorithm.

For a set of number

``````GCD(a_1,a_2,a_3,...,a_n) = GCD( GCD(a_1, a_2), a_3, a_4,..., a_n )
``````

Apply it recursively.

Same for LCM:

``````LCM(a,b) = a * b / GCD(a,b)
LCM(a_1,a_2,a_3,...,a_n) = LCM( LCM(a_1, a_2), a_3, a_4,..., a_n )
``````
-
The BigInteger class has a gcd method. +1 for answering the question for a set of integers rather than just a pair. – James K Polk Nov 18 '10 at 1:21
``````int lcmcal(int i,int y)
{
int n,x,s=1,t=1;
for(n=1;;n++)
{
s=i*n;
for(x=1;t<s;x++)
{
t=y*x;
}
if(s==t)
break;
}
return(s);
}
``````
-
``````int gcf(int a, int b)
{
while (a != b) // while the two numbers are not equal...
{
// ...subtract the smaller one from the larger one

if (a > b) a -= b; // if a is larger than b, subtract b from a
else b -= a; // if b is larger than a, subtract a from b
}

return a; // or return b, a will be equal to b either way
}

int lcm(int a, int b)
{
// the lcm is simply (a * b) divided by the gcf of the two

return (a * b) / gcf(a, b);
}
``````
-
some explanation would be nice... – Jan Dvorak Aug 17 '14 at 9:39
This is an implementation of the Euclidean Algorithm. To find the GCF of two numbers, subtract the larger number from the smaller number while the two numbers are not equal. For example: Find the GCF of 6 and 10: 10 6 // 10 is larger than 6, so subtract 6 from 10; 4 6 // 6 is now larger than 4, so subtract 4 from 10; 4 2 // 4 is larger than 2, so subtract 2 from 4; 2 2 // the two numbers are now equal, and that's the GCF; The LCM in mathematics is simply the first number times the second number divided by their GCF. – user3026735 Aug 17 '14 at 13:11
in the answer, I mean. Not everyone reads comments. – Jan Dvorak Aug 17 '14 at 15:14
This is also a really slow implementation of `gcf`. Using `%` would make things much faster (and make this no different than two other answers). – Teepeemm Aug 18 '14 at 3:21

More simpler to understand:

``````{ int num1,num2;
int m1,m2,r;
cout<<"Enter two numbers: "<<endl;
cin>>num1>>num2;
if(num1>num2)
{
m1=num1;
m2=num2;
}
else
{
m1=num2;
m2=num1;
}
while(r!=0)
{ r=m1%m2; m1=m2; m2=r;
}
cout<<"result of gcd of two number is "<<m1<<endl;
int lcm= (num1*num2)/m1;
cout<<"result of lcm of two number is "<<lcm;
}
``````
-
``````int lcm(int x,int y){

int i=1;

while(true){

if(!(x*i)%y)
return x*i;

i++;
}
``````
-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}