This C program finds the GCD (Greatest Common Divisor) and LCM (Least Common Multiple) of two numbers using recursion. Recursion is a technique where a function calls itself to solve a smaller version of the same problem. The GCD is computed with the classic recursive Euclidean algorithm, and the LCM is then derived from it using a simple mathematical identity.
The Key Idea
For any two positive integers, GCD(a, b) × LCM(a, b) = a × b. So once we know the GCD, the LCM is just:
LCM = (a / GCD) × b
The recursive Euclidean rule for GCD is: GCD(a, b) = GCD(b, a % b), stopping when b becomes 0.
The Program
#include <stdio.h>
/* Recursive Euclidean algorithm for GCD. */
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int main(void)
{
int num1, num2, g, lcm;
printf("Enter two numbers : ");
scanf("%d %d", &num1, &num2);
g = gcd(num1, num2);
lcm = (num1 / g) * num2; /* divide first to avoid overflow */
printf("GCD of %d and %d is : %d\n", num1, num2, g);
printf("LCM of %d and %d is : %d\n", num1, num2, lcm);
return 0;
}
How the Program Works
gcd() calls itself with (b, a % b) each time. The remainder shrinks on every call until b is 0, at which point a holds the GCD — this is the recursive base case.- The LCM uses the identity above. We divide
num1 / g before multiplying by num2 to reduce the risk of integer overflow on large inputs.
- This is far cleaner than the original textbook version, which counted upwards with a
static variable inside the recursion — correct but confusing and slow.
Sample Output
Enter two numbers : 8 12
GCD of 8 and 12 is : 4
LCM of 8 and 12 is : 24
For a clear explanation of recursion and the Euclidean algorithm, The C Programming Language by Kernighan and Ritchie is the classic reference — find it on Amazon.
This post contains affiliate links. If you buy through them, we may earn a small commission at no extra cost to you.
Related C Programs
Try it instantly in one of the best online C compilers, or set up a local toolchain with our complete C development environment guide.
