Given two non negative integers a and b, write a program to find Greatest common divisor (GCD) of both the numbers.

Problem Note

  • GCD of 2 integers a and b is defined as the greatest integer k such that k is a divisor of both a and b.
  • Both a and b fit in a 32 bit signed integer.
  • Do not use library functions.

Example 1

Input: a = 54, b = 24
Output: 6
Explanation: The number 54 can be expressed as a product of two integers in several different ways. 
The divisors of 54 are: 1, 2, 3, 6, 9, 18, 27, 54
The divisors of 24 are: 1, 2, 3, 4, 6, 8, 12, 24
The numbers that these two lists share in common are the common divisors of 54 and 24 are: 1, 2, 3, 6
The greatest of these is 6 which is the greatest common divisor of 54 and 24.