Skip to main content

How to Calculate Greatest Common Divisor (GCD) in Python

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest positive integer that divides two or more integers without leaving a remainder. It is a fundamental concept used in simplifying fractions, cryptography, and various algorithmic problems.

This guide explores how to calculate the GCD in Python using the built-in math module (the recommended approach) and the classical Euclidean algorithm.

Understanding GCD​

The GCD of two integers, a and b, is the largest number that divides both a and b perfectly.

Example:

  • Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
  • Factors of 18: 1, 2, 3, 6, 9, 18
  • GCD(48, 18) is 6.

Python provides a highly optimized, standard library function for this: math.gcd(). It is efficient and handles edge cases (like negative numbers or zero) correctly according to mathematical conventions.

import math

num1 = 48
num2 = 18

# ✅ Calculate GCD
result = math.gcd(num1, num2)

print(f"The GCD of {num1} and {num2} is: {result}")

Output:

The GCD of 48 and 18 is: 6
note

Python 3.9+ Update: Starting from Python 3.9, math.gcd() accepts an arbitrary number of arguments (e.g., math.gcd(10, 20, 30)). In older versions (3.8 and below), it strictly accepts only two arguments.

Method 2: The Euclidean Algorithm (Manual Implementation)​

If you are in a coding interview or working in an environment without the math module, you can implement the GCD logic manually using the Euclidean Algorithm.

The principle is efficient: GCD(a, b) = GCD(b, a % b). You repeat this until b becomes 0.

Iterative Implementation​

This is the most memory-efficient manual approach.

def euclidean_gcd(a, b):
    while b:
        # Swap a with b, and b with the remainder of a / b
        a, b = b, a % b
    return a

print(f"GCD of 100 and 25: {euclidean_gcd(100, 25)}")
print(f"GCD of 48 and 18: {euclidean_gcd(48, 18)}")

Output:

GCD of 100 and 25: 25
GCD of 48 and 18: 6

Recursive Implementation​

This is a cleaner representation of the mathematical definition but uses more stack memory.

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

print(f"Recursive GCD: {recursive_gcd(48, 18)}")

Output:

Recursive GCD: 6

Method 3: GCD of a List of Numbers​

Often you need to find the common divisor for an entire array of numbers.

Python 3.9+ Approach​

Pass all numbers as arguments to math.gcd.

import math

numbers = [24, 48, 36]

# ✅ Unpack the list using the * operator
result = math.gcd(*numbers)

print(f"GCD of {numbers}: {result}")

Output:

GCD of [24, 48, 36]: 12

Python 3.8 and Older Approach​

If you are on an older version, use functools.reduce to apply the GCD function cumulatively across the list.

import math
from functools import reduce

numbers = [24, 48, 36]

# Apply math.gcd to the first two, then the result with the third, etc.
result = reduce(math.gcd, numbers)

print(f"GCD via reduce: {result}")

Common Pitfalls: Floating Point Numbers​

The mathematical definition of GCD applies to integers. Passing floating-point numbers (even if they look like whole numbers, e.g., 10.0) to math.gcd will raise an error.

import math

try:
    # ⛔️ Incorrect: Passing floats
    print(math.gcd(10.5, 5))
except TypeError as e:
    print(f"Error: {e}")

try:
    # ⛔️ Incorrect: Passing integer-like floats
    print(math.gcd(10.0, 5.0))
except TypeError as e:
    print(f"Error: {e}")

Output:

Error: 'float' object cannot be interpreted as an integer
Error: 'float' object cannot be interpreted as an integer

Solution: Always convert inputs to integers using int() before calculation if there is a chance they might be floats.

Conclusion​

To calculate the Greatest Common Divisor in Python:

  1. Standard Use: Always use math.gcd(a, b) for reliability and speed.
  2. Multiple Numbers: Use math.gcd(*numbers) (Python 3.9+) or functools.reduce (older versions).
  3. Manual Logic: Use the Euclidean Algorithm (while b: a, b = b, a % b) if you cannot import modules.
  4. Data Types: Ensure inputs are integers; the function does not accept floats.

Table of Contents