GCD and LCM of Two Numbers in C – Euclid’s Algorithm

The GCD (Greatest Common Divisor) and LCM (Least Common Multiple) of two integers in C are most efficiently found using Euclid’s algorithm. The algorithm repeatedly replaces the larger number with the remainder of dividing the two numbers until the remainder is zero — what remains is the GCD. The LCM then follows from the identity LCM(a, b) = a × b / GCD(a, b). These two values appear throughout computer science: GCD in fraction simplification, cryptography (RSA), and modular arithmetic; LCM in scheduling and least-common-denominator problems.

How Euclid’s Algorithm Works — Step by Step

Find GCD of 12 and 8:

1. a = 12, b = 8 → remainder = 12 % 8 = 4 → set a = 8, b = 4
2. a = 8, b = 4 → remainder = 8 % 4 = 0 → set a = 4, b = 0
3. b = 0 → stop. GCD = 4

LCM = 12 / 4 × 8 = 24

Note: dividing by GCD before multiplying (a / g * b instead of a * b / g) prevents integer overflow when the product would exceed INT_MAX.

C Program for GCD and LCM

/* GCD and LCM of two integers in C — Euclidean algorithm
 * Compile: gcc -ansi -Wall -Wextra gcdlcm.c -o gcdlcm */
#include <stdio.h>

int gcd(int a, int b)
{
    int remainder;
    while (b != 0) {
        remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

int main(void)
{
    int num1, num2, g, l;

    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    g = gcd(num1, num2);
    l = num1 / g * num2;   /* divide first to prevent overflow */

    printf("GCD of %d and %d = %d\n", num1, num2, g);
    printf("LCM of %d and %d = %d\n", num1, num2, l);

    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra gcdlcm.c -o gcdlcm
./gcdlcm

Sample Input and Output

Test 1 — GCD = 4:

Enter two integers: 12 8
GCD of 12 and 8 = 4
LCM of 12 and 8 = 24

Test 2 — reversed order (same result):

Enter two integers: 8 12
GCD of 8 and 12 = 4
LCM of 8 and 12 = 24

Test 3 — GCD = 25:

Enter two integers: 100 75
GCD of 100 and 75 = 25
LCM of 100 and 75 = 300

Test 4 — coprime numbers (GCD = 1):

Enter two integers: 17 5
GCD of 17 and 5 = 1
LCM of 17 and 5 = 85

Test 5 — equal numbers:

Enter two integers: 6 6
GCD of 6 and 6 = 6
LCM of 6 and 6 = 6

Code Explanation

• while (b != 0) — Euclid’s algorithm terminates when the remainder is zero. At that point, a holds the GCD. The algorithm always terminates because each iteration strictly reduces b.
• remainder = a % b; a = b; b = remainder — the three-line core: save the remainder, shift b into a, and set b to the remainder. After two steps, both the old a and the old b have been discarded in favour of smaller values.
• Order independence — if you enter 8 and 12, the first iteration gives remainder = 8 % 12 = 8, then a = 12, b = 8. This is equivalent to starting with the larger number first; the algorithm self-corrects in one step.
• l = num1 / g * num2 — C evaluates left to right: num1 / g is exact integer division (g divides num1 by definition of GCD), and only then multiplied by num2. Writing num1 * num2 / g instead could overflow for large inputs.

Time and Space Complexity

Each iteration reduces the remainder by at least half (Fibonacci numbers give the worst case — O(log φ × min(a,b)) steps, where φ ≈ 1.618).

What This Program Teaches

• Euclid’s algorithm — one of the oldest algorithms in existence (circa 300 BC), still the standard approach for GCD in modern systems.
• Reducing a problem iteratively — the while loop shrinks the problem at each step until it reaches a trivially solved base case (b = 0).
• Overflow-safe arithmetic — a / gcd * b vs a * b / gcd is a practical lesson in ordering integer operations to avoid silent overflow bugs.
• Isolating logic in functions — separating gcd() from main() makes the program reusable and easier to test independently.

Related Programs

• GCD and LCM Using Recursion in C
• Factorial in C
• Prime Number Check in C
• Sum of Digits in C
• Armstrong Number in C

Recommended book:
The C Programming Language — Kernighan & Ritchie (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.