In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted gcd(x, y).

For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4

Euclidean Algorithm

The basic Euclidean algorithm for GCD is based on the below facts.

• If we subtract a smaller number from a larger (we reduce a larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
• Now instead of subtraction, if we divide the smaller number, the algorithm stops when we find remainder 0.

Recursive

1
2
3
4
5
6
7
8

#!/usr/bin/env python3

# Function to return gcd of a and b
def gcd(a, b):
    if a == 0 :
        return b

    return gcd(b%a, a)

Iterative

1
2
3
4
5
6
7
8

#!/usr/bin/env python3

# Function to return gcd of a and b
def gcd(a, b):
    while(a):
        a, b = b%a, a

    return b

Time Complexity

Time Complexity: O(log(min(a, b)))

Extended Euclidean Algorithm

Extended Euclidean algorithm also finds integer coefficients x and y such that: ax + by = gcd(a, b)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#!/usr/bin/env python3

# Function for extended Euclidean Algorithm
def gcd_extended(a, b):

    # Base Case
    if a == 0 :
        return b, 0, 1

    gcd, x1, y1 = gcd_extended(b%a, a)

    # Update x and y using results of recursive call
    x = y1 - (b//a) * x1
    y = x1

    return gcd, x, y

• The extended Euclidean algorithm is particularly useful when a and b are co-prime (Co-prime numbers are those numbers that have their GCD as 1).

Few Problems

Find GCD of nums more than two numbers (or array)

1
2
3
4
5
6
7

#!/usr/bin/env python3

arr = [2, 4, 6, 8]

gcd_num = gcd(arr[0], arr[1])
for i in range(2, len(arr)):
    gcd_num = gcd(gcd_num, arr[i])

Time Complexity: O(n * log(m)), where n is length of array and m is the smallest element of the array