How to find the greatest common divisor

In this article, we will discuss a very popular algorithm that is generally used in interview coding questions. The aim is to find the greatest common divisor (GCD) between two numbers. The optimized algorithm is pretty fast as compared to the brute force approach.

Greatest common divisor (GCD) using Euclid’s algorithm

The GCD of two integers (a, b), denoted by gcd(a,b), is defined as the largest positive integer d such that d | a and d | b where x | y implies that x divides y.

Example of GCD:

  • gcd(4, 8) = 4
  • gcd(10, 5) = 5
  • gcd(20,12) = 4

According to the Euclid’s Algorithm:

gcd(A,B) = gcd(B,A%B) // recurrence for GCD

gcd(A,0) = A // base case

Let’s discuss the proof of the recurrence.

Proof:

  • If a = bq + r.
  • Let d be any common divisor of a and b, which implies d|a and d|b implies that d|(a – bq) which in turn implies that d|r.
  • Let e be any common divisor of b and r, which implies that e|b , e|r which in turn implies that e|(bq + r)
  • This way, we can get e|a. Hence, any common divisor of a and b must also be a common divisor of r, and any common divisor of b and r must also be a divisor of a, which implies that d is a common divisor of a and b if, and only if, d is a common divisor of b and r.

The GCD of more than 2 numbers, e.g., gcd(a,b,c) is equal to gcd(a,gcd(b,c)) and so on.

int gcd(int a, int b) {
  return (b == 0 ? a : gcd(b, a % b));
}
int main() {
  // your code goes here
  int a = 100, b = 20;
  int result;
  result = gcd(a,b);
  cout << result;
}

Explanation:

  • The above function, gcd(), accepts two numbers as input and provides the output. As we are using the % operator, the number of recursive calls required to reach the final result would be less than n where n = max(a,b).
  • Euclid’s GCD algorithm runs in O(log(N))O(log(N)), where NN = max(a,b)max(a,b).

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)