C Program to Find LCM of Two Numbers

To find the LCM of two numbers in C, use the formula LCM = (a * b) / GCD(a, b) where GCD is the greatest common divisor calculated using the Euclidean algorithm.

Examples

Inputa = 4, b = 6

OutputLCM = 12

Inputa = 15, b = 20

OutputLCM = 60

Inputa = 7, b = 3

OutputLCM = 21

How to Think About It

To find the LCM of two numbers, first find their GCD using the Euclidean algorithm which repeatedly subtracts or uses modulo until the remainder is zero. Then use the formula LCM = (a * b) / GCD because the product of two numbers equals the product of their GCD and LCM.

Algorithm

1

Get input values for two numbers a and b

2

Calculate GCD of a and b using Euclidean algorithm

3

Calculate LCM using the formula (a * b) / GCD

4

Print the LCM

Code

c

#include <stdio.h>

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

int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    int lcm = (a * b) / gcd(a, b);
    printf("LCM = %d\n", lcm);
    return 0;
}

Output

Enter two numbers: 15 20
LCM = 60

Dry Run

Let's trace the input a=15 and b=20 through the code

1

Calculate GCD

Start with a=15, b=20; b != 0, temp=20; b = 15 % 20 = 15; a = 20 Next: a=20, b=15; b != 0, temp=15; b = 20 % 15 = 5; a = 15 Next: a=15, b=5; b != 0, temp=5; b = 15 % 5 = 0; a = 5 Loop ends, GCD = 5

2

Calculate LCM

LCM = (15 * 20) / 5 = 300 / 5 = 60

3

Print Result

Output: LCM = 60

a	b	temp	a % b
15	20	20	15
20	15	15	5
15	5	5	0

Why This Works

Step 1: Finding GCD

The Euclidean algorithm finds the greatest common divisor by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder is zero.

Step 2: Using GCD to find LCM

The product of two numbers equals the product of their GCD and LCM, so dividing the product by the GCD gives the LCM.

Step 3: Output the LCM

After calculating, the program prints the LCM to the user.

Alternative Approaches

Using a loop to find LCM

c

#include <stdio.h>

int main() {
    int a, b, max, lcm;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    max = (a > b) ? a : b;
    lcm = max;
    while (1) {
        if (lcm % a == 0 && lcm % b == 0) {
            printf("LCM = %d\n", lcm);
            break;
        }
        lcm++;
    }
    return 0;
}

This method uses a simple loop to find the smallest number divisible by both inputs but is slower for large numbers.

Recursive GCD function

c

#include <stdio.h>

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

int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    int lcm = (a * b) / gcd(a, b);
    printf("LCM = %d\n", lcm);
    return 0;
}

This uses recursion for GCD calculation, which is elegant and concise but may use more stack space.

Complexity: O(log(min(a,b))) time, O(1) space

Time Complexity

The Euclidean algorithm for GCD runs in O(log(min(a,b))) time, which dominates the calculation. Multiplying and dividing are constant time operations.

Space Complexity

The program uses constant extra space for variables and does not allocate additional memory.

Which Approach is Fastest?

Using the GCD-based formula is much faster than looping through multiples, especially for large numbers. Recursive GCD is elegant but uses more stack space.

Approach	Time	Space	Best For
GCD formula (Euclidean)	O(log(min(a,b)))	O(1)	Efficient for all inputs
Loop checking multiples	O(a*b) worst	O(1)	Simple but slow for large numbers
Recursive GCD	O(log(min(a,b)))	O(log(min(a,b))) stack	Clean code, small inputs