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.