Finding the GCD and LCM (the Euclidean Algorithm)

This lesson covers finding the greatest common divisor and least common multiple in C using the Euclidean algorithm, so you understand a mathematical algorithm using recursion. It's for anyone searching "C GCD LCM implementation."

The Euclidean algorithm is an ancient, efficient algorithm for finding the greatest common divisor (GCD) of two numbers. It keeps repeating "divide the larger by the smaller and take the remainder" until the remainder is 0.

The example's gcd() function keeps calling itself as gcd(b, a % b) until b == 0. Since the least common multiple relates to the GCD as a * b / gcd(a, b), lcm() reuses the GCD result to compute it.

A common early mistake is not knowing the relationship between GCD and LCM. Once you have the GCD, finding the LCM is easy with just multiplication and division.

This is a well-known algorithm frequently used to practice writing recursive functions, packed with both mathematical and programming fundamentals.

📖 Reference code

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int main(void) {
    printf("GCD: %d\n", gcd(12, 18));
    printf("LCM: %d\n", lcm(4, 6));
    return 0;
}

✍️ Your code

Type your code, then press "Run"

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