C program to find LCM of two numbers

Finding the Least Common Multiple (LCM) of two numbers is a fundamental task in mathematics and computer science. The LCM of two integers is the smallest positive integer that is perfectly divisible by both numbers. This article will guide you through writing a C program to find the LCM of two numbers using different methods.

Introduction

The LCM of two numbers is crucial in various applications, such as solving problems involving fractions, scheduling tasks, and more. The most common methods to find the LCM are using the HCF (GCD) and the incremental approach.

Methods to Find LCM

Using HCF (GCD)

The relationship between the LCM and HCF (GCD) of two numbers a and b is given by:

This method first calculates the HCF of the two numbers and then uses it to find the LCM.

Using Incremental Approach

In this method, we start with the larger of the two numbers and keep incrementing it by itself until it is divisible by both numbers. This approach is straightforward but less efficient compared to using HCF.

C Program Using HCF (GCD) Method

Here is a C program that finds the LCM of two numbers using the HCF (GCD) method:

#include <stdio.h>

// Function to find HCF using Euclidean algorithm
int findHCF(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1, num2;

    // Taking input from the user
    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    // Finding HCF
    int hcf = findHCF(num1, num2);

    // Calculating LCM
    int lcm = (num1 * num2) / hcf;

    // Displaying the result
    printf("LCM of %d and %d is %d", num1, num2, lcm);

    return 0;
}

Output

Enter two integers: 5 7
LCM of 5 and 7 is 35

Explanation:

1. Input: The program takes two integers as input from the user.
2. Function findHCF: Implements the Euclidean algorithm to compute the HCF.
3. LCM Calculation: Uses the relationship between HCF and LCM to compute the LCM.
4. Output: The LCM is displayed to the user.

C Program Using Incremental Approach

Here is a C program that finds the LCM of two numbers using the incremental approach:

#include <stdio.h>

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

    // Taking input from the user
    printf("Enter two integers: ");
    scanf("%d %d", &num1, &num2);

    // Finding the maximum of the two numbers
    max = (num1 > num2) ? num1 : num2;

    // Incremental approach to find LCM
    lcm = max;
    while (1) {
        if (lcm % num1 == 0 && lcm % num2 == 0) {
            break;
        }
        lcm += max;
    }

    // Displaying the result
    printf("LCM of %d and %d is %d", num1, num2, lcm);

    return 0;
}

Output

Enter two integers: 5 7
LCM of 5 and 7 is 35

Explanation:

1. Input: The program takes two integers as input from the user.
2. Maximum Calculation: Determines the larger of the two numbers.
3. Incremental Approach: Starts from the maximum number and keeps incrementing it until it finds a common multiple.
4. Output: The LCM is displayed to the user.