# C Program to Find the LCM of two Numbers

## C Program to find LCM of two numbers:-

The LCM of two integers n1 and n2 is the smallest positive integer that is perfectly divisible by both n1 and n2 (without a remainder). For example, the LCM of 140 and 120 is 840.

## 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

```#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

```#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

### Method 3 Code

```#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.

### Method 4 Code

```#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.

### Method 5 Code

```#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 5 Code

```#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```

### 10 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;
}

• 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);
}

• 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

• 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);
}

• 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);
}

• 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;
}

• 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);
}
}
}

• 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’);

}

}

• 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