C Program for LCM and HCF

Finding the HCF (Highest Common Factor) and LCM (Least Common Multiple) of two numbers is a classic and very important problem in C programming. It is commonly asked in beginner C interviews, college exams, and logic-building practice.

In this tutorial, you’ll learn:

• What HCF and LCM are
• The logic behind calculating them
• A step-by-step algorithm
• A complete C program with explanation

---

What is HCF (Highest Common Factor)?

The HCF of two numbers is the largest number that divides both numbers exactly.

Example:

• Numbers: 12 and 18
• Common factors: 1, 2, 3, 6
• HCF = 6

---

What is LCM (Least Common Multiple)?

The LCM of two numbers is the smallest number that is a multiple of both numbers.

Example:

• Numbers: 12 and 18
• Common multiples: 36, 72, ...
• LCM = 36

---

Important Relationship Between HCF and LCM

There is a very useful formula:

LCM × HCF = Number1 × Number2

So once we find the HCF using C language, calculating the LCM becomes very easy using C programing.

---

Algorithm to Find HCF and LCM

Step 1:

Take two integers as input.

Step 2:

Find the HCF using a loop (or Euclidean Algorithm).

Step 3:

Calculate LCM using the formula:

LCM = (num1 × num2) / HCF

---

How HCF is Calculated (Logic)

We check all numbers from 1 to the smaller of the two numbers and find the largest number that divides both.

---

C Program to Find HCF and LCM of Two Numbers

#include <stdio.h>

int main() {
    int num1, num2, i, hcf = 1;
    long lcm;

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

    // Find HCF
    for(i = 1; i <= num1 && i <= num2; i++) {
        if(num1 % i == 0 && num2 % i == 0) {
            hcf = i;
        }
    }

    // Calculate LCM
    lcm = (num1 * num2) / hcf;

    // Output results
    printf("HCF of %d and %d = %d\n", num1, num2, hcf);
    printf("LCM of %d and %d = %ld\n", num1, num2, lcm);

    return 0;
}

---

Output Example

Enter two numbers: 12 18
HCF of 12 and 18 = 6
LCM of 12 and 18 = 36

---

Time and Space Complexity

• Time Complexity: O(min(num1, num2))
• Space Complexity: O(1)

---

Optimized Approach (Using Euclidean Algorithm)

For better performance, HCF can also be calculated using the Euclidean Algorithm, which works faster for large numbers.

Formula:

HCF(a, b) = HCF(b, a % b)

This approach is commonly preferred in real-world applications.

---

Why This Program Is Important?

• Builds strong loop and conditional logic
• Frequently asked in C interviews
• Helps understand number theory basics
• Used as a base for advanced problems

---

Choosing the Right HCF and LCM Approach

For small numbers, a simple loop is easy to understand, but the Euclidean algorithm is the better general-purpose technique for finding HCF. Once the HCF is known, LCM can be calculated using:

LCM(a, b) = |a × b| / HCF(a, b)

In C, use long long when the input range can make the product a × b exceed the limits of an int. For production code, also define how zero and negative inputs should be handled instead of assuming only positive integers.

Worked Example: 18 and 24

1. HCF(18, 24) = 6.
2. LCM(18, 24) = (18 × 24) / 6 = 72.
3. Verify the result: 72 is divisible by both 18 and 24.

Common Mistakes in C Programs

• Using the wrong loop boundary and missing a possible factor.
• Calculating LCM before finding a correct HCF.
• Ignoring zero or negative input cases.
• Using int when the multiplication can overflow.
• Forgetting to test equal numbers, prime numbers, and numbers where one divides the other.

Useful Test Cases

Input	HCF	LCM	Why Test It
18, 24	6	72	Standard example
7, 13	1	91	Both are prime
12, 12	12	12	Equal values
8, 24	8	24	One number divides the other

Conclusion

The C program to find HCF and LCM of two numbers is a fundamental problem that teaches mathematical logic and efficient coding practices. Once you understand the concept of HCF, calculating LCM becomes straightforward using a simple formula.

If you are interested in internal working of Coding Languages please refer following articles

• HashMap internal working in Java