This example uses Euclid's algorithm to calculate GCDs and LCMs. For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Calculate the greatest common divisor (GCD) and least common multiple (LCM) of two integers in Python

[This program calculates the greatest common divisor (GCD) and least common multiple (LCM) of two integers in Python]

GCD

The greatest common divisor of two integers is the largest integer that evenly divides them both. For example, GCD(180, 105) = 15 because 15 is the largest integer that divides evenly into both 180 and 105.

Euclid's Elements c. 300 BCE describes an efficient algorithm for calculating the greatest common divisor. The key idea is that the greatest common divisor of two numbers remains unchanged if you subtract the smaller number from the larger.

The algorithm uses the fact that, if A >= B, then GCD(A, B) = GCD(B, A mod B). To calculate the greatest common divisor, you simply repeat this operation until A mod B is zero, at which point the greatest common divisor is B. Here's the Python code:

def gcd(a, b): '''Use Euclid's algorithm to calculate the greatest common divisor (GCD) of two numbers.''' # Make a >= b. a = abs(a) b = abs(b) if (a < b): a, b = b, a # Pull out remainders. while True: remainder = a % b if remainder == 0: return b a = b b = remainder

This algorithm is sometimes called the "Euclidean algorithm" or "Euclid's algorithm."

LCM

The least common multiple (LCM) of two integers A and B is the smallest integer that is a multiple of both A and B. For example, LCM(36, 84) = 252 because 252 is the smallest integer into which both 36 and 84 divide evenly.

You can use the greatest common divisor to easily calculate the least common multiple. Suppose A = a * g and B = b * g where g = GCD(A, B) and a and b are the other factors of A and B. Then LCM(A, B) = A * B / GCD(A, B). Intuitively A * B contains two copies of the greatest common divisor (plus the other factors a and b) so you divide by the greatest common divisor to get the smallest multiple containing only 1 copy of the GCD.

Here's the Python code:

def lcm(a, b): '''Return the least common multiple (LCM) of two numbers.''' return a * b // gcd(a, b)

Download the example to see all of the details.