GCD of Two Numbers With Examples

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).

Problem Statement

Example 1:

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

Example 2:

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

1. Simple Approach

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.

2. Efficient Approach: Euclid’s Algorithm

The algorithm is based on the following facts.

1. When we subtract small numbers from larger numbers, the GCD remains the same. As we keep subtracting the larger of two numbers, we get the GCD.

2. As an alternative to subtraction, we can divide the smaller number and the algorithm stops when we find the remainder 0.

“

See how these approaches are implemented in different programming languages.

Click Here...