The GCD (greatest common divisor, also called HCF) of two numbers is the largest number that divides both of them exactly. The LCM (least common multiple) is the smallest number that both of them divide exactly. For 12 and 18, the GCD is 6 and the LCM is 36. In this lesson you will find the GCD and LCM with a loop, with the Euclidean algorithm, and with the math module.

Run the code in our online Python compiler. The compiler does not take keyboard input, so the examples use fixed values.

 

Method 1: check every number (simple loop)

Check every number from 1 up to the smaller of the two numbers, and remember the largest one that divides both.

a, b = 12, 18
gcd = 1

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

print(gcd)

Output:

6

This is easy to understand, but slow for big numbers.

 

Method 2: the Euclidean algorithm (fast)

The GCD of two numbers does not change if you replace the larger one with the remainder of dividing it by the smaller one. Repeat until the remainder is 0. The last non-zero number is the GCD.

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

print(gcd(48, 36))

Output:

12

Here is what happens for 48 and 36:

Step

a

b

Start

48

36

1 (48 % 36 = 12)

36

12

2 (36 % 12 = 0)

12

0

When b becomes 0, the loop stops and a (12) is the GCD.

 

Find the LCM from the GCD

The product of two numbers equals GCD × LCM, so:

LCM = (a × b) ÷ GCD

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

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

for a, b in [(12, 18), (48, 36), (17, 5), (100, 75)]:
    print(a, b, 'GCD =', gcd(a, b), 'LCM =', lcm(a, b))

Output:

12 18 GCD = 6 LCM = 36
48 36 GCD = 12 LCM = 144
17 5 GCD = 1 LCM = 85
100 75 GCD = 25 LCM = 300

For 17 and 5, which are prime, the GCD is 1, so the LCM is simply 17 × 5 = 85. We use // (floor division) so that the result is a whole number.

 

Method 3: using the math module

Python has ready-made functions.

import math

print(math.gcd(12, 18))
print(math.lcm(12, 18))

Output:

6
36

math.lcm() needs Python 3.9 or newer. In Python 3.9 and newer, both functions also accept more than two numbers:

import math

print(math.gcd(12, 18, 24))
print(math.lcm(4, 6, 10))
6
60

Which method should you use?

Method

Speed

Best for

Loop over every number

Slow for big numbers

Understanding the idea

Euclidean algorithm

Fast

Exams, interviews and real programs

math.gcd() and math.lcm()

Fast

Real programs

 

Take the numbers from the user (on your computer)

a = int(input('Enter the first number: '))
b = int(input('Enter the second number: '))
print('GCD:', gcd(a, b))
print('LCM:', lcm(a, b))

Our online compiler does not support input() yet, so use fixed values there.

 

Common mistakes

  • Starting the loop at 0. Division by zero raises an error. Start at 1.
  • Using / for the LCM. It gives a decimal number. Use //.
  • Computing the LCM by multiplying the numbers. a × b is a common multiple, but it is only the least one when the GCD is 1.
  • Using math.lcm on an old Python version. It does not exist before Python 3.9.

 

Practice questions

  1. Find the GCD and LCM of 24 and 36.
  2. Find the GCD of three numbers using your gcd() function.
  3. Reduce the fraction 48/60 to its simplest form.
  4. Check whether two numbers are co-prime (their GCD is 1).
  5. Find the smallest number that is divisible by all the numbers from 1 to 10.

 

FAQs

Are GCD and HCF the same?

Yes. Both names mean the largest number that divides the given numbers exactly.

How do you find the LCM of two numbers in Python?

Use a * b // gcd(a, b), or math.lcm(a, b) in Python 3.9 and newer.

What is the GCD of two prime numbers?

It is 1, because they have no common divisor other than 1.

 

PreviousNext