C Program to Find LCM of Two Numbers - Using GCD

Find LCM Using GCD

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

// Function to compute GCD using Euclid's algorithm
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a, b;
    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    int g = gcd(abs(a), abs(b));  // Compute GCD of absolute values
    long long lcm = (long long)abs(a) * abs(b) / g;

    printf("LCM of %d and %d = %lld\n", a, b, lcm);
    return 0;
}

Enter two integers: 15 20
LCM of 15 and 20 = 60
        

Practice: Find LCM

The Least Common Multiple of two integers is the smallest positive integer that is divisible by both numbers. Using Euclid’s algorithm for GCD ensures that the computation is efficient and accurate. The formula LCM(a, b) = |a × b| / GCD(a, b) is a standard way to calculate the LCM.