How to Find the LCM of Two Numbers in C: A Detailed Guide

In programming, certain problems and algorithms serve as foundational concepts, and one such essential concept is the Least Common Multiple (LCM). The LCM of two numbers in C is the smallest positive integer that is divisible by both numbers, and it has applications in various fields, from signal processing to problem-solving in number theory. 

Additionally, in top software development courses, understanding how to compute the LCM of two numbers in C effectively is considered an important skill for handling mathematical operations and optimizing algorithms. 

This blog will provide an in-depth explanation of multiple methods to calculate the LCM of two numbers in C. We’ll start with a solid understanding of the concept itself, then move on to several coding techniques, including using the formula involving GCD (Greatest Common Divisor), brute force loops, and recursion. 

By the end, you will be equipped with both theoretical knowledge and practical examples to solve LCM of two numbers in C language. 

What is the LCM of Two Numbers in C?

Before diving into the code, it’s crucial to grasp the underlying concept of the LCM of two numbers in C. The Least Common Multiple (LCM) of two integers is defined as the smallest positive integer that is divisible by both numbers. In simple terms, it’s the "smallest common multiple" shared by the two numbers. 

For example:

• The LCM of 4 and 6 is 12, as 12 is the smallest number divisible by both 4 and 6.
• The LCM of 5 and 7 is 35, as 35 is the smallest number divisible by both 5 and 7.

LCM vs GCD: 

It's important to differentiate between LCM and GCD. While the GCD (Greatest Common Divisor) finds the largest number that divides both numbers, the LCM finds the smallest number that both numbers divide. These concepts are related mathematically by the following formula:

LCM(a,b) = GCD(a,b) / ∣a×b∣​ 

This formula provides an efficient way to compute the LCM once we know the GCD. For smaller numbers, you can simply calculate multiples until a match is found, but using the GCD is the most optimal method.

Must Explore: Introduction to C Tutorial

Why Do We Need to Find the LCM?

The LCM of two numbers in C is not just a theoretical concept; it has practical applications in various domains of computer science and engineering:

1. Scheduling Problems: In tasks such as synchronizing multiple events or processes, you may need to find the LCM to determine when two processes will coincide. For instance, if two events repeat every 5 and 7 days respectively, the LCM of 5 and 7 gives you the next day both events will occur together.
2. Signal Processing: In signal processing, periodic functions often need to be synchronized. The LCM of their periods provides a common point where both signals align again.
3. Fraction Operations: When performing arithmetic on fractions, the LCM of the denominators is used to find a common denominator for addition and subtraction operations.
4. Data Synchronization: In embedded systems or hardware design, multiple processes or timers may be running at different intervals. The LCM helps synchronize them by determining the smallest time unit where all intervals will match.

As you can see, calculating the LCM of two numbers in C is a valuable skill in solving real-world problems efficiently.

Must Read: 29 C Programming Projects in 2025 for All Levels [Source Code Included]

The Different Methods To Find LCM of Two Numbers in C

Before you start with the code, you should understand the operators, and loops in C programming. Otherwise, additional complexities can be created during execution, as well as debugging procedure. Addition to this, the functions in C is also a crucial concept before creating LCM of two numbers in C program. 

Method 1: Using the Formula (LCM and GCD) 

The most efficient method for calculating the LCM of two numbers in C involves using the relationship between the LCM and GCD (Greatest Common Divisor). This method leverages the fact that:

LCM(a,b)=∣a×b∣GCD(a,b)\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} 

By first calculating the GCD, we can then compute the LCM using this formula.

Code Implementation

#include <stdio.h>

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

// Function to find LCM using the formula LCM = (a * b) / GCD(a, b)
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

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

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

Step-by-Step Explanation:

1. GCD Function:
2. • We implement the Euclidean algorithm for computing the GCD of two numbers. This algorithm is efficient and runs in O(log⁡min⁡(a,b))O(\log \min(a, b)) time complexity.
   • The algorithm repeatedly reduces the problem by replacing the larger number with the remainder when the larger number is divided by the smaller one, until the remainder is zero.
2. LCM Function:
3. • The LCM of two numbers is calculated using the formula (a×b)/GCD(a,b)(a \times b) / \text{GCD}(a, b). This method works efficiently because it avoids checking multiples manually.
3. Main Function:
4. • The program takes input for two integers from the user, computes the LCM using the lcm() function, and displays the result.

Example Output:

Enter two numbers: 12 15
LCM of 12 and 15 is 60

Also Explore: What are Data Structures in C & How to Use Them?

Method 2: Using a Loop (Brute Force Approach)

A simpler but less efficient method for calculating the LCM of two numbers in C involves manually checking multiples of one number to see if they are divisible by both. This brute-force method is easy to understand, though it’s not optimal for large numbers.

Code Implementation

#include <stdio.h>

// Function to find LCM using brute force method
int lcm(int a, int b) {
    int max_num = (a > b) ? a : b;  // Start from the larger number
    while (1) {
        if (max_num % a == 0 && max_num % b == 0) {
            return max_num;
        }
        max_num++;
    }
}

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

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

Step-by-Step Explanation:

1. LCM Function:
2. • We start from the larger of the two numbers and check if it’s divisible by both a and b.
   • If it is divisible, that number is the LCM.
   • If not, we increment the number by 1 and continue checking.
2. Main Function:
3. • The program accepts two numbers as input, passes them to the lcm() function, and prints the result.

Example Output: 

Enter two numbers: 12 15
LCM of 12 and 15 is 60

Check out the Executive Diploma in Data Science & AI with IIIT-B!

Method 3: Using a While Loop (Multiples Method)

Another alternative approach is to use multiples. We begin with the larger number and check if it’s divisible by both numbers. If it isn’t, we keep incrementing the number until we find the smallest common multiple.

Code Implementation

#include <stdio.h>

// Function to find LCM using multiples method
int lcm(int a, int b) {
    int multiple = a > b ? a : b;
    while (multiple % a != 0 || multiple % b != 0) {
        multiple++;
    }
    return multiple;
}

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

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

Step-by-Step Explanation:

1. LCM Function:
2. • We start by assigning the larger number between a and b to multiple.
   • We check if the multiple is divisible by both a and b. If so, we return it as the LCM.
   • Otherwise, we keep incrementing the multiple and re-check until we find the LCM.
2. Main Function:
3. • Input is taken from the user, and the program calls the lcm() function to compute the result.

Example Output:

Enter two numbers: 12 15
LCM of 12 and 15 is 60

Method 4: Using Recursion

A recursive approach can also be used to find the LCM of two numbers in C by first calculating the GCD recursively and then applying the LCM formula. 

Code Implementation

#include <stdio.h>

// Recursive function to find GCD
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

// Function to find LCM using the formula LCM = (a * b) / GCD(a, b)
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

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

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

Step-by-Step Explanation:

1. Recursive GCD Function:
2. • This function calls itself recursively until the second number, b, becomes 0.
   • At that point, a will be the GCD of the two numbers.
2. LCM Function:
3. • The LCM is calculated using the formula (a×b)/GCD(a,b)(a \times b) / \text{GCD}(a, b), with the GCD function being called recursively.
3. Main Function:
4. • The main function takes input from the user, calls the lcm() function, and displays the result.

Example Output:

Enter two numbers: 12 15
LCM of 12 and 15 is 60

Pursue DBA in Digital Leadership from Golden Gate University, San Francisco!

Real-Life Applications of LCM

The LCM of two numbers in C is more than just a mathematical concept—it's widely

applicable in real-life scenarios:

• Task Scheduling: In task scheduling or event synchronization, the LCM is used to find when two periodic tasks will occur simultaneously again.
• Digital Signal Processing: In signal processing, the LCM is used to synchronize signals with different frequencies.
• Fraction Operations: Adding and subtracting fractions requires calculating the LCM of the denominators to find a common denominator.
• Timing Systems in Embedded Systems: Systems with multiple timers can use the LCM to determine the first time all timers will expire together.

Conclusion 

The ability to calculate the LCM of two numbers in C is a crucial skill for programmers, especially when working with number theory, fractions, or systems requiring synchronization. Whether you are solving problems in math, working on signal processing, or designing embedded systems, understanding and efficiently calculating the LCM will make your solutions more robust.

In this guide, we explored multiple methods to compute the LCM of two numbers in C, including:

1. The formula-based method using GCD.
2. The brute force approach using loops.
3. The multiple-checking approach with while loops.
4. The elegant recursive approach.

We also discussed real-life applications of LCM and provided optimization tips for better performance. By mastering these techniques, you’ll be well-equipped to handle a variety of computational challenges involving the LCM of two numbers in C.

FAQs 

1. Can we calculate the LCM of two numbers using recursion?

Answer: Yes, we can calculate the LCM of two numbers in C using recursion. This can be achieved by first finding the GCD recursively, then using the formula:

LCM(a,b)=GCD(a,b) / ∣a×b∣​

The GCD can be calculated recursively using the Euclidean algorithm, which divides the problem down into smaller subproblems. After obtaining the GCD, the LCM is simply the product of the two numbers divided by the GCD.

Here’s an example code:

#include <stdio.h>

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

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    printf("LCM of %d and %d is %d\n", a, b, lcm(a, b));
    return 0;
}

The recursive approach adds clarity and elegance to the algorithm, though it may not be as efficient as the iterative version for very large numbers due to the overhead of function calls.

2. What if one of the numbers is zero? How does the LCM calculation handle this? 

Answer: If either of the numbers is zero, the LCM of two numbers in C is undefined, because the LCM is the smallest positive integer divisible by both numbers. Since zero is divisible by any number, there's no finite LCM that can be calculated when one of the numbers is zero.

In practice, you can add a check to handle this scenario and print an error or return 0:

int lcm(int a, int b) {
    if (a == 0 || b == 0) {
        printf("LCM is undefined for zero.\n");
        return 0;
    }
    return (a * b) / gcd(a, b);
}

3. How can I optimize the brute force method to improve performance? 

Answer: The brute force approach for calculating the LCM of two numbers in C involves checking each multiple of the larger number until it is divisible by both numbers. This method is inefficient for large numbers. One optimization would be to avoid incrementing one by one. Instead, start by checking the multiples of the larger number.

A more optimized brute force approach would only check multiples of the larger number:

int lcm(int a, int b) {
    int multiple = (a > b) ? a : b;
    while (multiple % a != 0 || multiple % b != 0) {
        multiple += (a > b) ? a : b;
    }
    return multiple;
}

This reduces the number of checks by incrementing by the larger number, not just 1.

4. How does the LCM formula relate to the concept of divisibility?

Answer: The LCM of two numbers is related to the concept of divisibility because it is the smallest number that is divisible by both numbers. The formula for LCM:

LCM(a,b)=GCD(a,b) / ∣a×b∣​

works by ensuring that the result is divisible by both a and b. The GCD finds the largest divisor shared by both numbers, and dividing the product of the numbers by the GCD ensures we only include the unique prime factors, thus minimizing the number to the least multiple common to both.

5. Can I find the LCM of more than two numbers in C?

Answer: Yes, the LCM of more than two numbers can be found by iteratively calculating the LCM of pairs of numbers. If you want to calculate the LCM of three numbers, a, b, and c, you can first find the LCM of a and b, then use that result to calculate the LCM of the result with c.

Here’s a simple example of how to extend it:

int lcm_of_three(int a, int b, int c) {
    return lcm(lcm(a, b), c);
}

The LCM of more than two numbers can also be extended similarly using this pairwise method.

6. Is there a way to optimize LCM for very large numbers in C? 

Answer: For very large numbers, it’s crucial to use an efficient algorithm for calculating the LCM of two numbers in C. The formula involving GCD is already quite efficient, but you can further optimize it by handling big numbers with care:

1. Avoid large intermediate products: When multiplying large numbers a and b, try to handle the multiplication in parts or use data types that handle arbitrarily large integers (like long long or libraries like GMP for arbitrary-precision arithmetic).
2. Early stopping in the brute force method: For large numbers, it’s better to stop checking as soon as you find the first multiple divisible by both numbers.
3. Modular Arithmetic: If you're calculating LCM in modular arithmetic (as in cryptography or large-scale computations), use modular exponentiation to ensure that numbers don't overflow.

7. What data types are best suited for storing the LCM of large numbers?

Answer: The data type best suited for storing the LCM of two numbers in C depends on the size of the numbers involved: 

• For numbers that fit within the standard int range (typically up to 2 billion in C), int is sufficient.
• For larger numbers, use long long int, which allows you to store much larger values (up to 9 quintillion in most systems).
• If you're working with extremely large numbers, beyond the range of long long int, you’ll need a library like GMP (GNU Multiple Precision Arithmetic Library) to handle arbitrary-precision integers.

Here’s an example using long long:

long long lcm(long long a, long long b) {
    return (a * b) / gcd(a, b);
}

8. Can I use the LCM in applications like scheduling or event synchronization? 

Answer: Yes, the LCM of two numbers in C is extremely useful in scheduling and event synchronization. For example, if you need two tasks to occur at periodic intervals, the LCM of their individual intervals gives you the point when both tasks will occur at the same time.

For example, if one task occurs every 6 minutes and another every 8 minutes, the LCM(6, 8) = 24 minutes is when both tasks will align again.

This is especially relevant in real-time systems and embedded programming, where periodic events need to be coordinated.

9. Why do we use the absolute value in the LCM formula? 

Answer: The absolute value in the LCM formula ensures that the result is always positive, regardless of whether the input numbers are positive or negative. Since the LCM is defined as the smallest positive integer divisible by both numbers, the absolute value is necessary to avoid a negative result when dealing with negative integers.

For example, the LCM of -5 and 10 should be 10, not -10, because the LCM is always positive.

10. Are there any specific optimizations for LCM in low-level programming?

Answer: Yes, there are several optimizations in low-level programming for calculating the LCM of two numbers in C:

1. Avoiding large intermediate results: When dealing with very large numbers, try to minimize the multiplication operations to prevent overflow.
2. Using bitwise operations: For certain cases (especially with powers of 2), bitwise shifts and operations can be used to compute the LCM faster.
3. Precomputing common results: If you are calculating the LCM of the same pairs of numbers repeatedly, precomputing and storing results in an array or hash table can save time.

11. Can the LCM be calculated efficiently for a large set of numbers?

Answer: Yes, calculating the LCM of a large set of numbers can be done efficiently by iteratively applying the LCM formula for pairs. The general approach is:

LCM(a1​,a2​,a3​,...,an​) = LCM(LCM(a1​,a2​),a3​,...,an​) 

This method allows you to calculate the LCM of many numbers without having to check all multiples individually, ensuring that the time complexity remains manageable.

Take a Free C Programming Quiz

Answer quick questions and assess your C programming knowledge

Start Quiz