C Program to Find GCD (HCF) and LCM of Two Numbers

This program calculates the Greatest Common Divisor (GCD), also known as Highest Common Factor (HCF), and the Least Common Multiple (LCM) of two integers entered by the user.

Concept Overview

The GCD of two numbers is the largest number that divides both without leaving a remainder. The LCM is the smallest number that is a multiple of both numbers. Once the GCD is known, the LCM can be calculated using the relationship LCM × GCD = a × b.

Program

#include <stdio.h>

// Function to calculate GCD
int gcd(int a, int b) {
    while(b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1, num2, hcf, lcm;

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

    hcf = gcd(num1, num2);
    lcm = (num1 * num2) / hcf;

    printf("GCD (HCF) = %d\n", hcf);
    printf("LCM = %d\n", lcm);

    return 0;
}

Sample Output

Enter two numbers: 12 18
GCD (HCF) = 6
LCM = 36

Explanation

• The Euclidean algorithm repeatedly replaces the larger number by the remainder of dividing the larger by the smaller until the remainder becomes zero.
• At that point, the smaller number is the GCD.
• LCM is computed using the formula `(a × b) / GCD`.
• This approach is efficient and works for all positive integers.