Finding the GCD and LCM (the Euclidean algorithm)

This lesson covers the Euclidean algorithm in R, with the aim of understanding a mathematical algorithm built on recursion.

The Euclidean algorithm is an ancient, efficient way of finding the greatest common divisor (GCD) of two numbers: take the remainder of the larger divided by the smaller, and repeat the same calculation until the remainder is zero.

In the sample code, gcd_func() calls itself as gcd_func(b, a %% b) until b == 0. The least common multiple follows from the relationship (a * b) / gcd_func(a, b), which lcm_func() uses.

A common early stumble is not knowing the relationship between the GCD and the LCM. Once you have the GCD, one multiplication and one division give you the LCM.

It is a famous algorithm packed with the fundamentals of both mathematics and programming, and a very common subject for practising recursion.

📖 Reference code

gcd_func <- function(a, b) {
  if (b == 0) return(a)
  gcd_func(b, a %% b)
}

lcm_func <- function(a, b) {
  (a * b) / gcd_func(a, b)
}

cat("GCD:", gcd_func(12, 18), "\n")
cat("LCM:", lcm_func(4, 6), "\n")

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run R directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).