Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach 1
3.
Approach 2(Using GCD)
4.
FAQs:
5.
Key Takeaways: 
Last Updated: Mar 27, 2024

LCM of 2 numbers in C

Author Nishant Rana
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

LCM stands for Least Common Multiple. It is the smallest number that is divisible by both numbers.

It is represented by LCM(a, b) or lcm(a, b) where a and b are the two numbers of which we need to find the LCM.

 

Example:

LCM(4, 8) = 8

LCM(3, 5) = 15

LCM(20, 48) = 240

 

Also Read, Binary to Hex Converter,C Static Function,  Also Read - Strong number in c

Approach 1

We will follow the following steps to find the LCM of two numbers (A and B):

  1. We will make a max_div variable and store the maximum of A and B in it.
  2. We will run a while loop until we find the LCM.
  3. We will check if max_div is the LCM of A and B. If it is divisible by both then we will break and display max_div, else we will increment max_div.

 

Refer to the below implementation of the above approach.

#include <stdio.h>  

void main()  
{  
    int num1 = 18, num2 = 12, max_div, flag = 1;   
      
    // max_div variable holds the max divisible number between num1 and num2.  
    max_div = (num1 > num2) ? num1 : num2;  
      
    while (flag) // (flag = 1)  
    {  
        if (max_div % num1 == 0 && max_div % num2 == 0)  
        {  
            printf( " The LCM of %d and %d is %d. ", num1, num2, max_div);  
            break;  
        }  
        ++max_div; // pre-increment max_div  
    }  
}  

Output:

The LCM of 18 and 12 is 36. 

 

Time Complexity: The time complexity of the above approach is O(A * B) (where A and B are the two numbers). It is because in the worst case, the while loop will run for A * B times.

Space Complexity: The space complexity of the above approach is O(1) because we are not using any auxiliary space.

You can also read about dynamic array in c, and  Tribonacci Series

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 2(Using GCD)

GCD  stands for Greatest Common Divisor. It is the greatest integer that divides both the numbers. We can calculate the LCM using the GCD of the numbers.

Let us say gcd is the GCD of the two numbers (A, B). 

We can find the LCM of A and B using the following formula: (A * B)/gcd

Refer to the below implementation of the above approach.
 

#include <stdio.h>  
#include <conio.h>  
  
// use Recursive function to return gcd of two numbers num1 and num2.  
int gcd( int num1, int num2)  
{  
    if ( num1 == 0)  // if num1 is equal to 0, return num2  
          
        {  
        return num2;      
        }  
    return gcd (num2 % num1, num1);  
}  
  
// lcm_fun () function returns the LCM of two numbers  
int lcm_fun( int num1, int num2)  
{   // divide the num1 by gcd() function and then multiply with num2.  
    return ( num1 / gcd(num1, num2)) * num2;  
}  
  
int main()  
{   // declaration and initialization of positive numbers  
    int num1 = 18, num2 = 12;  
  
    printf ( " LCM of two numbers %d and %d is %d ", num1, num2, lcm_fun( num1, num2));  
    return 0;  
}  

Output:

The LCM of 18 and 12 is 36. 

 

Time Complexity: The time complexity of the above approach is O(log(max(A, b)).

Space Complexity: The space complexity of the above approach is O(1).

You can practice by yourself with the help of online c compiler.

Must Read what is storage class in c and Decision Making in C

FAQs:

  1. What is LCM?
    LCM stands for Least Common Multiple. It is the smallest number that is divisible by both numbers.
  2. What iss GCD?
    GCD  stands for Greatest Common Divisor. It is the greatest integer that divides both the numbers. 

Key Takeaways: 

In this article, we have extensively discussed the following things:

  1. We first discussed what is LCM.
  2. Then we discussed various approaches to calculate the LCM of two numbers(a, b).
     

We hope that this blog has helped you enhance your knowledge regarding LCM of two numbers and if you would like to learn more, check out our articles here. Do upvote our blog to help other ninjas grow. Happy Coding!




 

Previous article
Magic number in C
Next article
Digital Clock using C
Live masterclass