
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
