C Program to Find the LCM of Two Numbers

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).

LCM_of_two_numbers

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

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.

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.

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 150+ 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;
    }


  • 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


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


  • 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