Find GCD in C

What You’ll Learn

GCD is a classic interview warm-up: remainders, loops, and the Euclidean algorithm. This tutorial covers the definition of gcd(a, b), iterative and recursive C programs, a live preview, algorithm steps, worked C examples, edge cases, and complexity.

📝 Problem & Approach

Given two integers a and b, compute their greatest common divisor using the Euclidean algorithm.

/* Remainder chain for gcd(48, 18)
 * gcd(48, 18) = gcd(18, 12)
 *             = gcd(12,  6)
 *             = gcd( 6,  0)
 *             = 6
 */

Inputs & Outputs

Minimal workflow

function gcd(a, b):  // assume nonnegative; define gcd(0,0) as needed
    while b != 0:
        (a, b) = (b, a mod b)
    return a

Method comparison

🔮 Live Preview

Enter two integers and compute gcd using the same Euclidean recurrence as the C samples.

Press “Compute gcd”.

Examples Gallery

Two complete C programs — iterative and recursive Euclidean — both for 48 and 18. Click View Output to reveal sample console results.

#include <stdio.h>

int find_gcd(int num1, int num2) {
    while (num2 != 0) {
        int temp = num2;
        num2 = num1 % num2;
        num1 = temp;
    }
    return num1;
}

int main(void) {
    int number1 = 48;
    int number2 = 18;
    int g;

    g = find_gcd(number1, number2);
    printf("GCD of %d and %d is: %d\n", number1, number2, g);

    return 0;
}

GCD of 48 and 18 is: 6

#include <stdio.h>

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

int main(void) {
    int number1 = 48;
    int number2 = 18;

    printf("GCD of %d and %d is: %d\n", number1, number2,
           gcd_recursive(number1, number2));

    return 0;
}

GCD of 48 and 18 is: 6

🔎 Worked Walkthrough — gcd(48, 18)

Trace the Euclidean remainder chain until the remainder is zero.

So gcd(48, 18) = 6. Reducing 18/48 by dividing by 6 yields 3/8.

🔄 Sample Values

Known results for common interview pairs.

🎯 Practice Problems

Try these variations to lock in the pattern.

Notes

⏱️ Time and Space Complexity

Lamé’s theorem bounds the number of division steps for inputs with a fixed number of digits.

💡 Best Practices