Home / Python / Example programs / Loops and numbers

Python program: Greatest common divisor and least common multiple

Find the GCD and LCM of two numbers with Euclid's algorithm.

The code

import math

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

def lcm(a, b):
    return a * b // gcd(a, b)

print(gcd(48, 36), lcm(48, 36))
print(math.gcd(48, 36), math.lcm(48, 36))   # built in since Python 3.9

Output

12 144
12 144

How it works

Euclid's algorithm replaces (a, b) with (b, a mod b) until b is 0: over 2,000 years old and still the fastest simple method. LCM follows from GCD.

Learn the ideas behind it in the free lesson Loops.