GCD and LCM

We learned about LCM and GCD in our 6/7th Standard. The example on WikiPedia explains the GCD, the way we learn it in school.
First, we represent both the number as product of prime numbers.
Then pick the common number, which appear in both the product representation.
Finally, we multiply all the common factors to get the GCD.


Writing a program to calculate GCD based on above algorithm can be a complex and sometimes very slow. Luckily there are algorithms and trick to calculate GCD.

LCM also follows somewhat similar calculation, but if we know the GCD of the 2 numbers we can easilt calculate LCM using 3 simple steps.
1) Calculate product of 2 given numbers.
2) Calculate GCD of those 2 numbers.
3) Divide the product by GCD and we get LCM given 2 numbers.

Here is a simple code in C++ to calculate LCM and GCD using Euclidean algorithm
 

#include <iostream>
#include <assert.h>

using namespace std;

namespace Math {

    int gcd ( int high, int low ) {
        assert ( high != 0 );
        assert ( low != 0 );
        assert ( high > low );

        if ( low == 1 || low == high )
            return low;

        int remainder = high % low;

        if ( remainder == 0 ) {
            return low;
        }
        high = low;
        low = remainder;
        return gcd( high, low );
    }

     int lcm ( int high, int low ) {
        assert ( high != 0 );
        assert ( low != 0 );
        assert ( high > low );

        long product = low * high;
        int gcd = Math::gcd ( high, low );

        return product/gcd;
     }
}

using namespace Math;

int main ( int argc, char* argv[] ) {

  int int_gcd, int_lcm;

  int_gcd = gcd( 20, 10 );
  assert( int_gcd == 10 );
  printf( "GCD( %d, %d) = %d \n", 20, 10, int_gcd );
  int_gcd = gcd( 95, 5 );
  assert ( int_gcd == 5 );
  printf( "GCD( %d, %d) = %d \n", 95, 5, int_gcd );

  int_gcd = gcd ( 49, 14 );
  assert ( int_gcd == 7 );
  printf( "GCD( %d, %d) = %d \n", 49, 14, int_gcd );

 int_lcm = lcm ( 100, 10 );
  printf( "LCM( %d, %d) = %d \n", 100, 10, int_lcm );

  int_lcm = lcm ( 218912312, 67223434 );
  printf( "LCM( %d, %d) = %d \n", 218912312, 67223434, int_lcm );

}

Above program produces following output:

GCD( 20, 10) = 10 
GCD( 95, 5) = 5 
GCD( 49, 14) = 7 
LCM( 100, 10) = 100 
LCM( 218912312, 67223434 ) = 966336792

Refreneces: GCD LCM Euclidean algorithm