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.