GCD Program in Python

Problem statement

Find the greatest common divisor of two numbers — the largest integer that divides both exactly. GCD is also called HCF.

Approach 1: simple loop

Search downwards from the smaller number: the first value that divides both numbers exactly is the GCD. Simple, and it shows what "common divisor" means.

a, b = 48, 18

gcd = 1
for i in range(min(a, b), 0, -1):
    if a % i == 0 and b % i == 0:
        gcd = i
        break

print(gcd)
# Output: 6

The loop starts at min(a, b) because no divisor of both can exceed the smaller number, and it stops at the first hit — the greatest one.

Approach 2: reusable function

Euclid's algorithm is the classic: repeatedly replace the pair (a, b) with (b, a % b) until b becomes 0; the remaining a is the GCD. Dramatically faster than searching.

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

print(gcd(48, 18))   # 6
print(gcd(100, 75))   # 25
print(gcd(17, 5))     # 1 — coprime

Each step shrinks the numbers fast — the remainder is always smaller than the divisor — so even huge pairs finish in a handful of iterations.

Approach 3: Pythonic alternative

The standard library ships the algorithm: math.gcd(). There is also math.lcm() next to it for the partner concept.

import math

print(math.gcd(48, 18))          # 6
print(math.gcd(48, 18, 24))      # 6 — takes any number of arguments

Know Euclid's version by hand for exams; trust this one in real code.

Dry run

Trace gcd(48, 18) through Euclid's loop. Start: a=48, b=18. Step 1: a,b = 18, 48%18 = 18, 12. Step 2: a,b = 12, 18%12 = 12, 6. Step 3: a,b = 6, 12%6 = 6, 0. Now b is 0 — loop ends, answer is a = 6. Check it: 6 divides both 48 (8 times) and 18 (3 times), and nothing larger does.

Common errors

Forgetting to update both variables together — a = b then b = a % b uses the already-changed a; the tuple assignment a, b = b, a % b avoids this.
A loop that never ends because the remainder step is missing — always shrink with %.
Searching upward from 1 — you find a common divisor, but the greatest one appears last.
Confusing GCD with LCM: LCM(4, 6) is 12, GCD(4, 6) is 2. The product identity gcd × lcm = a × b is a good sanity check.
Not handling zero: gcd(n, 0) is n by definition, and Euclid's loop already gets that right.

Practice on PyDebug

Turn the idea into a debugging habit with these free browser exercises: