How to find GCD of two numbers in Python?

General Discussions
,
1

How can I calculate the greatest common divisor (GCD) in Python?

The greatest common divisor (GCD) of two numbers, a and b, is the largest number that divides both without leaving a remainder. Euclid’s algorithm is an efficient method for finding the GCD, based on the observation that if r is the remainder when a is divided by b, then:

gcd(a, b) = gcd(b, r)

The base case for this algorithm is: gcd(a, 0) = a

Write a function called gcd that takes two parameters, a and b, and returns their greatest common divisor using gcd python.

2

Hey Everyone! Here is the detailed explanation

“Using Euclid’s Algorithm (Iterative Approach)”

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

# Example usage
print(gcd(48, 18))  # Output: 6

This iterative approach efficiently computes the GCD by repeatedly replacing a with b and b with a % b until b becomes zero.

3

“Adding to @akanshasrivastava.1121 explanation, here’s Euclid’s Algorithm implemented using recursion.”

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

# Example usage
print(gcd(48, 18))  # Output: 6

This recursive implementation mirrors the mathematical definition, calling itself with gcd(b, a % b) until the base case (b == 0) is reached. It’s a concise and elegant alternative to the iterative approach.

4

“Building on the earlier examples, Python also provides a built-in function for this task, making things even simpler.”

import math

def gcd(a, b):
    return math.gcd(a, b)

# Example usage
print(gcd(48, 18))  # Output: 6

Python’s math.gcd is highly optimized under the hood. If you don’t need to understand the algorithm’s mechanics, this built-in function is the best choice for readability and efficiency.