Finding GCD and LCM

The best way to find GCD of two numbers is by using Euclid's Algorithm.

 

Which also could be written as

Below is a simple implementation of Euclid's algorithm in C++,

        #include
        using namespace std;

        int gcd(int a, int b)
        {
                if(b==0) return a;
                return gcd(b,a%b);
        }
        int main()
        {
                cout << "GCD of 84 and 18 is " << gcd(84,18) << endl;
        }
Output:
        GCD of 84 and 18 is 6.

GCD and LCM are related by a very simple equation,

This way the problem of computing the least common multiple can be reduced to the problem of computing the greatest common divisor (GCD).

The above code can be modified to include LCM function as,

        #include
        using namespace std;

        int gcd(int a, int b)
        {
                if(b==0) return a;
                return gcd(b,a%b);
        }
        int lcm(int a, int b)
        {
                return a*b/gcd(b,a%b);
        }
        int main()
        {
                cout << "GCD of 84 and 18 is " << gcd(84,18) << endl;
                cout << "LCM of 84 and 18 is " << lcm(84,18) << endl;
        }

Output:
        GCD of 84 and 18 is 6.
        LCM of 84 and 18 is 252.