C Program to Find the LCM of Two Numbers

September 29, 2022

LCM of Two Number

The LCM of Two Number num1 and num2 is the smallest positive integer that is perfectly divisible by both num1 and num2 (without a remainder).

Various Method covered

This post explains the following methods –

Method 1: A linear way to calculate LCM
Method 2: Modified interval Linear way
Method 3: Simple usage of HCF calculation to determine LCM
Method 4: Repeated subtraction to calculate HCF and determine LCM
Method 5: Recursive repeated subtraction to calculate HCF and determine LCM
Method 6: Modulo Recursive repeated subtraction to calculate HCF and determine LCM

Method 1

For a input num1 and num2. This method uses two following observations –

LCM of two numbers will at least be equal or greater than max(num1, num2)
Largest possibility of LCM will be num1 * num2

When iterating in (i) We can linearly find an (i) that is divisible by both num1 & num2

Method 1 Code

Run

#include<stdio.h>

int main()
{
    int num1 = 36, num2 = 60, lcm;

        // finding the larger number here
        int max = (num1 > num2)? num1 : num2;
        
        // LCM will atleast be >= max(num1, num2)
        // Largest possibility of LCM will be num1*num2
        for(int i = max ; i <= num1*num2 ; i++)
        {
            if(i % num1 == 0 && i % num2 == 0){
                lcm = i;
                break;
            }
        }
    
    printf("The LCM: %d", lcm);
    
    return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)

Output

The LCM: 180

Method 2

For input num1 and num2. This method uses two following observations –

Rather than linearly checking for LCM by doing i++. We can do i = i + max
Starting with i = max (num1, num2)
The next possibility of LCM will be ‘max’ interval apart

Method 2 Code

Run

#include<stdio.h>

int main()
{
    int num1 = 36, num2 = 60, lcm;

        // finding the larger number here
        int max = (num1 > num2)? num1 : num2;
        
        // can do i++ here
        // but,  i = i + max is done as next possibility of LCM will be
        // max interval apart
        for(int i = max ; i <= num1*num2 ; i=i+max)
        {
            if(i % num1 == 0 && i % num2 == 0){
                lcm = i;
                break;
            }
        }
    
    printf("The LCM: %d", lcm);
    
    return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)

Output

The LCM: 180

Method 3

For this method, you need to know how to calculate HCF, check this post here

Main Idea This method uses the idea that we can calculate the LCM by rather calculating the HCF. As below relationship exist between the two.

LCM * HCF = product of two numbers
LCM * HCF = num1 * num2

Method 3 Code

Run

#include<stdio.h>
int main()
{
    int num1 = 16, num2 = 24, hcf = 1;
    
    // calculating HCF here
    for(int i = 1; i <= num1 || i <= num2; i++) {
        if(num1%i == 0 && num2%i == 0 )
            hcf = i;
    }
    
    // LCM formula
    int lcm = (num1*num2)/hcf;
    
    printf("The LCM: %d", lcm);
    
    return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)

Output

The LCM: 48

Method 4

For this method, you need to know how to calculate HCF, check this post here

We use repeated subtraction (Euclidean Algorithm) to calculate the HCF.

Main Idea Let m = 144, n = 32

m > n
m = m – n = 144 – 32 = 112
now m = 112, n = 32

m = m – n = 112 – 32 = 80
now m = 80, n = 32

m = m – n = 80 – 32 = 48
now m = 48, n = 32

m = m – n = 48 – 32 = 16
now m = 16, n = 32

Since, m < n
We will do subtraction in opposite fashion.

n = n – m = 32 – 16 = 16
now m = 16, n = 16

m = n. So, stop. HCF = 16

Method 4 Code

Run

#include<stdio.h>

int getHCF(int num1, int num2){
    
    // using repeated subtraction here
    while (num1 != num2)
    {
        if (num1 > num2)
            num1 -= num2;
        else
            num2 -= num1;
    }
    
    return num1;
}

int main()
{
    int num1 = 144, num2 = 32;
    
    int hcf = getHCF(num1, num2);
    printf("The HCF: %d\n", hcf);
    
    // LCM formula
    int lcm = (num1*num2)/hcf;
    printf("The LCM: %d", lcm);
    
    return 0;
}
// Time Complexity : O(N)
// Space Complexity : O(1)

Output

The HCF: 16
The LCM: 288

Method 5

This method uses recursion.

For this method, you need to know how to calculate HCF, check this post here

We use repeated subtraction (Euclidean Algorithm) to calculate the HCF.

Main Idea Previous Codes didn't handle the case when one of the numbers is 0.

The HCF of two numbers by definition when one number is 0, is the other non zero number

Example: HCF of 0 and 6 will be 6
We will handle this case in the below program as well.

Method 5 Code

Run

#include<stdio.h>
// Recursive function for repeated subtraction HCF calculation
int getHCF(int num1, int num2)
{
    // Handles the case when one of the number is 0 (num1) 
    // Check alert above in explanation
    if (num1 == 0)
       return num2;
    
    // Handles the case when one of the number is 0 (num2)
    // Check alert above in explanation
    if (num2 == 0)
       return num1;
  
    // base case
    if (num1 == num2)
        return num1;
  
    // num1 is greater
    if (num1 > num2)
        return getHCF(num1 - num2, num2);

    return getHCF(num1, num2 - num1);
}

int main()
{
    int num1 = 144, num2 = 32;
    
    int hcf = getHCF(num1, num2);
    printf("The HCF: %d\n", hcf);
    
    // LCM formula
    int lcm = (num1*num2)/hcf;
    printf("The LCM: %d", lcm);
    
    return 0;
}

Output

The HCF: 16
The LCM: 288

Method 6

This method uses recursion.

In Addition, we are using modulo operation to reduce the number of subtractions required and improve the time complexity

For this method, you need to know how to calculate HCF, check this post here

We use repeated Modulo Recursive subtraction (Euclidean Algorithm) to calculate the HCF.

Method 6 Code

Run

#include<stdio.h>

// This method improves complexity of repeated substraction
// By efficient use of modulo operator in euclidean algorithm
int getHCF(int a, int b)
{
    return b == 0 ? a : getHCF(b, a % b);   
}

int main()
{
    int num1 = 144, num2 = 32;
    
    int hcf = getHCF(num1, num2);
    printf("The HCF: %d\n", hcf);
    
    // LCM formula
    int lcm = (num1*num2)/hcf;
    printf("The LCM: %d", lcm);
    
    return 0;
}
// Time Complexity: log(max(a,b))

Output

The HCF: 16
The LCM: 288

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

11 comments on “C Program to Find the LCM of Two Numbers”

Ashruti
#include
int main(){
int a,b,i,gcd,lcm;
printf(“Enter two positive integers:”);
scanf(“%d%d”,&a,&b);

for(i=0; i<=a && i<=b; i++){
//check if i is a factor of both integers
if(a%i==0 && b%i==0)
gcd=i;
}
lcm=(a*b)/gcd;
printf("The LCM of two number %d and %d is %d.",a,b,lcm);
return 0;
}

3

Log in to Reply
Sushil
#include
#include
int main()
{
int n1,n2;
printf(“Enter two number:\n”);
scanf(“%d\n%d”,&n1,&n2);
int i,lcm;
for(i=1;i<=n1 && i<=n2;i++)
{
if(n1%i==0 && n2%i==0)
{
lcm=(n1*n2)/i;
}
}
printf("Lcm is %d",lcm);
}

1

Log in to Reply
Mousmi
#include
int LCM(int x, int y);//function to find the LCM
int result=0;
int main()
{
int a,b; //numbers to find the lcm
printf(“Enter the value of a: \n”);
scanf(“%d”, &a);
printf(“Enter the value of b: \n”);
scanf(“%d”, &b);
result=LCM(a,b);//function calling and storing the return type
printf(“Result=%d” , result);
return 0;
}
int LCM(int x,int y)
{
for(int i=1; i<=y; i++)
{
if(x%i==0 && y%i==0)
int result = i;
printf("Lcm of aand b= ", result);
}
return 0;}

#C CODE

0

Log in to Reply
221910308017
#include
int main()
{
int a,b,i,lcm;
a=12;
b=14;
lcm=(a>b)?a:b;
while(1)
{
if(lcm%a==0 && lcm%b==0)
{
printf(“LCM of %d %d=%d”,a,b,lcm);
break;
}
++lcm;
}
return(0);
}

0

Log in to Reply
rathod
#include
void main()
{
int a, b,i,LCM;
printf(“enter the value of a”);
scanf(“%d”,&a);
printf(“enter the value of b”);
scanf(“%d”,&b);
for(i=1;i<=a||i<=b,i++)
{
if(i*a==i*b)
LCM=i*a;
}
printf("lcm of numbers is =%d",LCM);
}

0

Log in to Reply
sachin
#include
using namespace std;
int getLCM(int a, int b){
int m;
m = (a > b) ? a : b;
while(true){
if(m % a == 0 && m % b == 0)
return m;
m++;
}
}
int getLCMArray(int arr[], int n){
int lcm = getLCM(arr[0], arr[1]);
for(int i = 2; i < n; i++){
lcm = getLCM(lcm, arr[i]);
}
return lcm;
}
int main() {
int arr[] = {4, 6, 12, 24, 30};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "LCM of array elements: " << getLCMArray(arr, n);
}

0

Log in to Reply
Timy
#include
int main()
{
int a, b, hcf, lcm, i;
a=10;
b=8;
for(i=1; i<=a&&i<=b; i++)
if(a%i==0&&b%i==0)
{ hcf=i;
}
lcm =(a*b)/hcf;
printf("lcm is %d",lcm);
return 0;
}

3

Log in to Reply
Suraj
#include
using namespace std;
int LCM(int x, int y);//function to find the LCM
int main(){
int a,b; //numbers to find the lcm
cin>>a>>b;
int result=LCM(a,b);//function calling and storing the return type
cout<<result<<endl;
}
int LCM(int x,int y){
for(int i=1;i<=y;i++){
for(int j=1;j<=x;j++){
if((x*i)==(y*j))
return(x*i);
}
}
}

0

Log in to Reply

HelpPrepInsta
Thanks for contributing the code Suraj

0

Log in to Reply

ajit
in java:::::::

import java.util.Scanner;

public class Main
{

public static void main(String args[])
{

Scanner sc = new Scanner(System.in);

int choice = ‘n’;

do {

System.out.println(“Enter the two number to find LCM ?”);
int num1 = sc.nextInt();
int num2 = sc.nextInt();

System.out.println(“value of num1 :: ” + num1);
System.out.println(“value of num2 :: ” + num2);

int max = 0;

if (num1 > num2) {
max = num1;
} else {
max = num2;
}

System.out.println(“value of maximum :: ” + max);

boolean flag = true;

while (flag == true) {
if ((max % num1 == 0) && (max % num2 == 0)) {

System.out.println(“Lcm of ” + num1 + ” and ” + num2 + ” is :: ” + max);
flag = false;

}

max++;

}

System.out.println(“do you want to perform this operation again ?”);
choice = sc.next().charAt(0);

}while(choice == ‘y’ || choice == ‘Y’);

}

}

1

Log in to Reply
Authority DMC
m,n=map(int,input().split())
for j in range(max(m,n),m*n+1,1):
if j%m==0 and j%n==0:
print(“LCM=”,j)
break
#python 3

3

Log in to Reply