GCD of Two Numbers in Python: 4 Methods Explained

GCD of two numbers is the largest integer that divides both inputs without a remainder. For 15 and 25, that number is 5; for 48 and 18, it is 6. Python gives you four methods to compute it, from a naive while loop to a single function call from the standard library.

What Is GCD and Why Placement Tests Use It

GCD stands for Greatest Common Divisor, also called HCF (Highest Common Factor). The formal definition: the GCD of two integers a and b is the largest positive integer d such that d divides a and d divides b with zero remainder.

Quick dry run for gcd(15, 25):

• Factors of 15: 1, 3, 5, 15
• Factors of 25: 1, 5, 25
• Common factors: 1, 5
• GCD = 5

Two real-world uses are worth knowing for context:

• Fraction reduction: to simplify 15/25, divide numerator and denominator by gcd(15, 25) = 5, giving 3/5.
• LCM calculation: LCM(a, b) = (a * b) // gcd(a, b). The GCD is the building block for finding the Lowest Common Multiple.

Placement coding rounds at companies like TCS and Infosys include GCD problems because one question exercises three skills simultaneously: loop or recursion control, the modulo operator, and complexity reasoning. If you can write a correct GCD implementation and explain why one approach is faster than another, you have demonstrated more signal than five trivial programs would.

Method 1: Naive Linear Scan

This approach checks every integer from 1 to min(a, b). Each candidate divisor that divides both numbers becomes the new GCD. The last one stored is the largest, which is the answer.

# GCD of two numbers — naive linear scan
num1 = int(input("Enter 1st number: "))
num2 = int(input("Enter 2nd number: "))

gcd = 1
i = 1
while i <= num1 and i <= num2:
    if num1 % i == 0 and num2 % i == 0:
        gcd = i
    i += 1

print("GCD is", gcd)

Dry run for gcd(25, 5):

• i=1: 25%1=0, 5%1=0. gcd=1.
• i=2: 25%2=1 (not zero). Skip.
• i=3: 25%3=1 (not zero). Skip.
• i=4: 25%4=1 (not zero). Skip.
• i=5: 25%5=0, 5%5=0. gcd=5.
• i=6: 6 > min(25,5)=5. Loop ends.
• Output: GCD is 5

The algorithm is correct but visits every integer up to min(a, b). For inputs like 100000 and 100001, that is 100000 iterations. The Euclidean methods below do the same job in fewer than 25.

Method 2: Recursive GCD Using Euclid’s Identity

Euclid’s algorithm rests on a single identity: gcd(a, b) = gcd(b, a mod b). When b reaches zero, a is the GCD. The recursion depth is bounded by O(log min(a, b)), so it handles large numbers without any practical stack-overflow risk.

# GCD of two numbers — recursion
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

a = int(input("Enter 1st number: "))
b = int(input("Enter 2nd number: "))
print("GCD is", gcd(a, b))

Trace for gcd(12, 36):

• gcd(12, 36): b is 36, recurse with gcd(36, 12%36=12)
• gcd(36, 12): b is 12, recurse with gcd(12, 36%12=0)
• gcd(12, 0): b is 0, return 12
• Output: GCD is 12

Three recursive calls for a 12:36 ratio. The naive scan would have checked 12 integers.

Method 3: Euclidean Algorithm, Iterative

The iterative version avoids function-call overhead. Python’s tuple assignment makes the swap a single line.

# GCD of two numbers — Euclidean algorithm, iterative
num1 = int(input("Enter 1st number: "))
num2 = int(input("Enter 2nd number: "))

a, b = num1, num2
while b:
    a, b = b, a % b

print("GCD is", a)

Dry run for gcd(15, 75):

• a=15, b=75: new a=75, new b=15%75=15. So a=75, b=15.
• a=75, b=15: new a=15, new b=75%15=0. So a=15, b=0.
• Loop ends. Output: GCD is 15

Two iterations for a 75:15 ratio. The naive scan would have checked 15 integers.

When a is less than b (for example, gcd(5, 25)), the first iteration swaps the pair automatically. The algorithm self-corrects without any manual input-ordering.

Method 4: Python’s Built-in math.gcd()

For production code or any placement test that allows standard library imports, math.gcd is the right choice. It has been in the standard library since Python 3.5 and handles edge cases like gcd(0, n) correctly by convention (returning n).

import math

a = int(input("Enter 1st number: "))
b = int(input("Enter 2nd number: "))
print("GCD is", math.gcd(a, b))

Python 3.9 extended math.gcd to accept more than two arguments:

import math

# GCD of three numbers
print(math.gcd(12, 18, 24))  # Output: 6

The math.gcd function also handles the case where one argument is zero. math.gcd(0, 18) returns 18. The naive while loop above would return 1 for gcd(0, 18) without an extra guard, making math.gcd the safer choice for production code where inputs are less predictable.

Which Method to Use

Method	When to use it	Time complexity
Naive while loop	Learning exercises only	O(min(a, b))
Recursive Euclidean	Interview requires recursion	O(log min(a, b))
Iterative Euclidean	Interview, no imports allowed	O(log min(a, b))
math.gcd()	Production code or tests with imports	O(log min(a, b))

For placement interviews: if the prompt says “write without built-ins”, use the iterative Euclidean method. It is the shortest correct solution and its complexity is defensible when the interviewer asks “can you do better?” If imports are allowed, math.gcd signals familiarity with the standard library.

For further Python programs that placement rounds bundle with GCD work, FACE Prep’s Python basic programs practice guide covers the full set. Recruiters frequently pair GCD with finding the greatest of three numbers and basic Python calculator operations in the same coding round.

The iterative Euclidean method shows something worth remembering: two lines of swap logic outperform a loop that checks every integer up to min(a, b). That same instinct, reduce the problem to its simplest form and call the right tool, transfers directly when you start wiring Python with LLM APIs. TinkerLLM runs Python exercises on live LLM backends for ₹299 full access, with no prior AI background required.