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

Facebook comments:

Site Owner: Sachin Goyal