Greatest Common Divisor(GCD) and Least Common Multiple (LCM)

GCD a number that divides the given numbers without any remainder. Naive idea to compute GCD is to try every number from 1 to smallest of the numbers as divisor and taking the maximum one which divides the numbers without any remainders. This technique is too slow. One clever method for this is to use technique given below. If you have numbers say 42 and 18 then first divide 42 by 18 and take the remainder which is 6. Next divide 18 by 6, no remainder, so GCD is 6. This technique is mentioned in programming pearls book by John Bentley.

  
int GCD(int a, int b){

 while( b != 0){
  a = a%b;
  std::swap(a,b);
 }
 return a;

}  

After being able to compute GCD, computing LCM is pretty easy. You juts multiply 2 numbers and divide it by the GCD. The code for calculating LCM is given below.

  
//calculate lcm
int lcm(int a, int b) {

 return a * b/ GCD(a,b);
}