Editor

Python Program to Find the GCD and LCM of Two Numbers

Beginner · Numbers · CBSE class 11 practical list

The GCD (greatest common divisor, also called the 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 into. This program finds the GCD with Euclid's method and then uses it to get the LCM.

Program

gcd_and_lcm.py
a = 36 # or: a = int(input("Enter the first number: "))
b = 60 # or: b = int(input("Enter the second number: "))
# Euclid's method: keep replacing (x, y) with (y, x % y) until y is 0
x = a
y = b
while y != 0:
remainder = x % y
x = y
y = remainder
gcd = x
# GCD x LCM is always equal to a x b
lcm = (a * b) // gcd
print("GCD (HCF) of", a, "and", b, "is", gcd)
print("LCM of", a, "and", b, "is", lcm)
Output
GCD (HCF) of 36 and 60 is 12
LCM of 36 and 60 is 180

How it works

  1. Euclid's method keeps replacing x with y, and y with the remainder x % y.
  2. The remainders get smaller each time, and when one becomes 0, the value left in x is the GCD.
  3. For two positive numbers, GCD x LCM = a x b, so the LCM is (a * b) // gcd.
  4. // is whole-number division, so the LCM comes out as an integer rather than a decimal.

Other ways to write it

Using the math module

Using the math module
import math
a = 36
b = 60
print("GCD of", a, "and", b, "is", math.gcd(a, b))
print("LCM of", a, "and", b, "is", math.lcm(a, b))
Output
GCD of 36 and 60 is 12
LCM of 36 and 60 is 180

math.gcd() and math.lcm() do the same work in one call each; math.lcm() needs Python 3.9 or newer.

By checking every divisor

By checking every divisor
a = 36
b = 60
gcd = 1
for i in range(1, min(a, b) + 1):
if a % i == 0 and b % i == 0:
gcd = i # the last common divisor found is the greatest
lcm = (a * b) // gcd
print("GCD:", gcd)
print("LCM:", lcm)
Output
GCD: 12
LCM: 180

This slower textbook approach tries every number up to the smaller one and keeps the last one that divides both.

Try it yourself

Change the numbers to 17 and 5 and see why their GCD is 1.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises