Python programs / Numbers / GCD and LCM

Python Program to Find the GCD and LCM of Two Numbers

Beginner Numbers

Finds the greatest common divisor (HCF) of two numbers with Euclid's algorithm, then their least common multiple from it.

The greatest common divisor (GCD) of two numbers, also called the highest common factor (HCF), is the biggest number that divides both exactly. Their least common multiple (LCM) is the smallest number that both divide into. For 48 and 18, the GCD is 6 and the LCM is 144. Euclid's algorithm, over 2,000 years old, finds the GCD in a few steps even for very big numbers, and the LCM follows from it.

Program

def gcd(a, b):
    """The greatest common divisor of a and b."""
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    """The least common multiple of a and b."""
    return a * b // gcd(a, b)


print("GCD of 48 and 18:", gcd(48, 18))
print("LCM of 48 and 18:", lcm(48, 18))

Open in the editor Download gcd_lcm.py

Output

GCD of 48 and 18: 6
LCM of 48 and 18: 144

How it works

  1. While b isn't 0, the pair a, b becomes b and the remainder of a divided by b. That remainder is a minus a multiple of b, so the new pair has the same common divisors as the old one, and the same GCD, but smaller numbers. Python works out both new values from the old ones before changing either.
  2. When b reaches 0, the GCD is a: every number divides 0, so the biggest number that divides both a and 0 is a itself.
  3. For any two positive numbers, GCD × LCM = a × b, so the LCM is their product divided by the GCD: 48 × 18 = 864, and 864 ÷ 6 = 144. // keeps the result a whole number, where / would give 144.0.
  4. The program prints the GCD and the LCM of 48 and 18.

For 48 and 18, the loop runs three times:

Step a b a % b
1 48 18 12
2 18 12 6
3 12 6 0

Then a is 6 and b is 0, so the loop stops: the GCD is 6.

Other ways to write it

With the math module

Python's math module has both: math.gcd(), and math.lcm() from Python 3.9. Since 3.9, both also take more than two numbers.

import math

print(math.gcd(48, 18), math.lcm(48, 18), math.lcm(4, 6, 10))

With recursion

The GCD of a and b is the GCD of b and a % b, so the function can call itself with those until b is 0 (recursion).

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

print(gcd(48, 18), gcd(17, 5))

Try it yourself

  • Find the GCD and LCM of 17 and 5. They share no divisor but 1, so the GCD is 1 and the LCM is their product, 85.
  • Swap the numbers, as gcd(18, 48): the first time round, the loop swaps them back, so the answer is the same.
  • Print a and b inside the loop to see the steps in the table above.
  • Find the GCD of three numbers, such as 24, 36 and 60, with gcd(gcd(24, 36), 60). It's 12.

More numbers programs

Share this program