Finding the GCD and LCM (the Euclidean algorithm)

This lesson covers the Euclidean algorithm in Objective-C, 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, gcdFunc() expresses the whole recursion in one line with a ternary operator: b == 0 ? a : gcdFunc(b, a % b). The least common multiple follows from the relationship a * b / gcdFunc(a, b), which lcmFunc() 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

NSInteger gcdFunc(NSInteger a, NSInteger b) {
    return b == 0 ? a : gcdFunc(b, a % b);
}

NSInteger lcmFunc(NSInteger a, NSInteger b) {
    return a * b / gcdFunc(a, b);
}

NSLog(@"GCD: %ld", (long)gcdFunc(12, 18));
NSLog(@"LCM: %ld", (long)lcmFunc(4, 6));

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Objective-C 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).