Euclidean Algorithm

The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers also divides their difference.

Algorithm

Given two integers $a$ and $b$, the algorithm repeatedly replaces the larger number by its remainder when divided by the smaller number until one of the numbers becomes zero. The non-zero number is the GCD.

Time Complexity

The time complexity is $O(\log (\min (a,b)))$, making it very efficient even for large numbers.

Implementation

def euclidean_algorithm(a, b):
    """Compute the GCD of two integers a and b using the Euclidean algorithm."""
    while b:
        a, b = b, a % b
    return a

# Example usage:
a = 48
b = 18
gcd = euclidean_algorithm(a, b)
print("The GCD of {} and {} is {}".format(a, b, gcd))