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)
def gcd(a, b): if b == 0: return a else: return gcd(b, a % b)
def gcd(a, b): while b != 0: a, b = b, a % b return a