Make delicious recipes!

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);   
        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,

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:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal