Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Given two numbers 'a' and 'b' find their GCD and LCM

GCD (Greatest Common Divisor) is the largest number that divides both 'A' and 'B'

LCM (Least Common Multiple) is the smallest number that is a multiple of 'A' as well as 'B'

Example: Let A=35 and B=42, then
A = 7 x 5,
B = 7 x 3 x 2

GCD (A,B) = 7 and
LCM (A,B) = 7x5x3x2 = 210

So, GCD is the product of all the common prime factors of A and B
While LCM is the product of all the unique prime factors of A and B

And since AxB is the product of all the prime factors of A and B (common factors being duplicated), it is clear that
A x B = GCD x LCM

## Algorithm to find GCD

Remember these two cool properties of GCD:
GCD (a, b) = GCD (a%b, b) if a >= b and
GCD (a,0) = a;

Using these, it is easy to calculate GCD as follows:
Code Example
```int gcd (int a, int b)
{
if (a==0)
return b;
if (b==0)
return a;
if (a > b)
return gcd (a%b, b);
else
return gcd (a, b%a);
}
```
```gcd (35, 42)
= gcd(35, 7)
= gcd(0, 7)
= 7

gcd (30, 50)
= gcd(30, 20)
= gcd(10, 20)
= gcd (10, 0)
= 10
```

## Algorithm to find LCM

Find GCD and then use,
LCM = AxB / GCD

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: