Python Program to Find GCD and LCM of Two Numbers

mediumFunctionsPython

Euclid's method finds the greatest common divisor quickly; the LCM then follows from a simple formula.

The question

Read two positive integers (one per line). Print their GCD on the first line and their LCM on the second. Use a loop or the Euclid method — do not import math.

The code

program.py

a = int(input())
b = int(input())
x, y = a, b
while y:
    x, y = y, x % y
gcd = x
lcm = a * b // gcd
print("GCD =", gcd)
print("LCM =", lcm)

Try it Yourself »

Input

16
112

Output

GCD = 16
LCM = 112

How it works

1Repeat (x, y) = (y, x % y) until y becomes 0. The value left in x is the GCD.
2LCM = a × b ÷ GCD. Using // keeps it a whole number.
3Work on copies x, y so the original a and b are still available for the LCM.

Common mistakes

Using / for the LCM, which prints 36.0 instead of 36.
Overwriting a and b during Euclid's loop and then computing the LCM from the changed values.

Now solve a similar question yourself

A new Python question every time, checked instantly.

Practice questions