Consider two +ve integers a and b. We must now find their GCD (greatest common divisor), i.e. the largest number that is a divisor of both a and b. It is denoted by gcd(a,b).

Input: a=32, b=20 Output: 4 Explanation: 4 is the largest factor dividing both numbers.

Input: a=98, b=70 Output: 14 Explanation: 14 is the largest factor dividing both numbers.

Simple approach entails traversing all the numbers from min(A, B) to 1 and checking whether or not the current number divides A and B. If it does, then it will be the GCD of A and B.

The algorithm is based on the following facts.

See how these approaches are implemented in different programming languages.