Greatest Common Divisor in C: Fast & Modern Methods

Finding the greatest common divisor in C is a classic problem that every developer encounters when studying algorithms, cryptography, or numerical programming. The greatest common divisor (GCD)—also known as the highest common factor (HCF)—of two non-zero integers is the largest positive integer that divides both numbers without leaving a remainder. For instance, the GCD of 48 and 18 is 6.

While the concept is straightforward, implementing it efficiently in C requires choosing the right algorithmic approach. Depending on your performance requirements and target hardware, you can solve this using simple loops, standard Euclidean division, recursion, or bitwise binary operations. This guide covers all of these methods, complete with clean code and edge-case handling.

The Naive Approach: Brute Force Loop

The most intuitive way to find the GCD of two numbers is to test every possible divisor starting from the smaller of the two inputs and moving downward to 1. The first common factor you encounter is guaranteed to be the greatest.

#include <stdio.h>

int gcd_brute_force(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    
    int min = (a < b) ? a : b;
    int gcd = 1;
    
    for (int i = min; i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
            break;
        }
    }
    return gcd;
}

While this approach works for small numbers, its time complexity is O(min(a, b)). If you calculate the GCD of two 64-bit numbers or large 32-bit primes, this function can freeze your program by performing billions of modulo iterations. Therefore, brute force should be avoided in real-world C applications.

Greatest Common Divisor in C Using the Euclidean Algorithm

Dating back to roughly 300 BC, Euclid's algorithm is one of the oldest numerical algorithms still in widespread use. It is based on a simple mathematical principle: the GCD of two integers a and b (where a > b) is identical to the GCD of b and the remainder of a divided by b (a % b).

Formally: GCD(a, b) = GCD(b, a % b). This process repeats until the remainder becomes zero, at which point the last non-zero divisor is your answer.

Iterative Euclidean Algorithm

The iterative variant is typically preferred in systems programming because it avoids function call overhead and stack allocations.

#include <stdio.h>
#include <stdlib.h>

int gcd_euclidean_iterative(int a, int b) {
    a = abs(a);
    b = abs(b);
    
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main(void) {
    int num1 = 252, num2 = 105;
    printf("GCD of %d and %d is: %d\n", num1, num2, gcd_euclidean_iterative(num1, num2));
    return 0;
}

This implementation runs in O(log(min(a, b))) time, requiring at most a few dozen operations even for numbers reaching billions.

Recursive Euclidean Algorithm

If you prefer concise and expressive code, the Euclidean approach can be written in a single line using the ternary operator:

#include <stdio.h>
#include <stdlib.h>

int gcd_euclidean_recursive(int a, int b) {
    return (b == 0) ? abs(a) : gcd_euclidean_recursive(b, a % b);
}

Modern compilers optimizing at -O2 or -O3 will automatically convert this tail-recursive function into a tight loop, producing assembly virtually identical to the iterative version.

Optimized Binary GCD (Stein's Algorithm)

The standard Euclidean algorithm relies heavily on the modulo operator (%), which performs integer division. On microcontrollers, embedded systems, and older hardware architectures, hardware division can be significantly slower than addition, subtraction, and bit shifting.

Josef Stein introduced the Binary GCD algorithm in 1967. It calculates the GCD using only bit shifts, bitwise ANDs, and subtractions:

• If both a and b are even, gcd(a, b) = 2 * gcd(a / 2, b / 2).
• If a is even and b is odd, gcd(a, b) = gcd(a / 2, b).
• If both are odd and a >= b, gcd(a, b) = gcd((a - b) / 2, b).

#include <stdio.h>
#include <stdlib.h>

unsigned int gcd_binary(unsigned int a, unsigned int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    // Find the greatest power of 2 that divides both a and b
    int shift = __builtin_ctz(a | b);

    // Divide a by 2 until it becomes odd
    a >>= __builtin_ctz(a);

    do {
        // Divide b by 2 until it becomes odd
        b >>= __builtin_ctz(b);

        // Ensure a <= b, then swap if necessary
        if (a > b) {
            unsigned int temp = a;
            a = b;
            b = temp;
        }
        
        b = b - a;
    } while (b != 0);

    return a << shift;
}

Note: The function __builtin_ctz (Count Trailing Zeros) is a GCC and Clang built-in that maps directly to fast CPU instructions like BSF or TZCNT on x86, making this implementation exceptionally fast in low-latency environments.

Crucial Edge Cases to Handle

Writing robust production-ready C code requires accounting for mathematically valid but tricky inputs:

1. Zeros: By mathematical definition, GCD(a, 0) = |a| because any non-zero integer divides 0. However, GCD(0, 0) is mathematically undefined. Most C implementations return 0 in this case.
2. Negative Numbers: GCD is conventionally defined as positive. Always sanitize inputs using abs() or by explicitly negating them before processing.
3. Integer Overflow (INT_MIN): In two's-complement arithmetic, abs(INT_MIN) invokes undefined behavior because the positive counterpart does not fit in a signed 32-bit integer. If you must process arbitrary signed integers across the full range, cast them to long long or unsigned int before calling abs().

Algorithm Comparison

Here is how the three main GCD algorithms compare in real-world scenarios:

• Brute Force: O(N) time, O(1) space. Only useful for learning and debugging very small numbers.
• Euclidean (Iterative): O(log N) time, O(1) space. The gold standard for readability, reliability, and portability across general-purpose CPUs.
• Binary (Stein's): O(log N) time, O(1) space. Best for high-throughput math routines, cryptographic engines, and embedded targets lacking native hardware division.

Summary

For 99% of C projects, the iterative Euclidean algorithm is the right tool: it is simple, immune to recursion depth issues, highly optimized by compilers, and easy for any maintenance programmer to understand. If you write low-level code for microcontrollers or tight cryptographic loops, consider Stein's binary algorithm to squeeze out the highest possible performance.