The Euclidean Algorithm

Published on in Algorithms

It is one of the most fundamental algorithm that helps us find the Greatest Common Divisor (GCD) also known as Highest Common Factor (HCF) for two numbers.

Recall that the Greatest Common Divisor (GCD) of two integers A and B is the largest integer that divides both A and B.

A naive approach would be to incrementally check each number below min(A, B) and see which is the highest number that divides both. But the problem can be broken down into smaller subproblems.

Bringing in Divide and Conquer

The Euclidean Algorithm is a technique for quickly finding the GCD of two integers. The algorithm is as follows -

  • If A = 0 then GCD(A,B) = B, since the GCD(0, B) = B, and we can stop.
  • If B = 0 then GCD(A, B) = A, since the GCD(A, 0) = A, and we can stop.
  • Write A in quotient remainder form (A = B⋅Q + R)
  • Find GCD(B, R) using the Euclidean Algorithm since GCD(A, B) = GCD(B, R)

Recursive Algorithm

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

Iterative Algorithm

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a