LCM of Two numbers in C

LCM of two numbers using Incremental Method

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.

• C

C

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

You can also try this code with Online C Compiler

Run Code

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

LCM of two numbers in C 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.

• C

C

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

You can also try this code with Online C Compiler

Run Code

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

LCM of two numbers in C using function

1. Function Declaration: We create a function that calculates the LCM using loops.
2. Inputs: The function accepts two integer numbers as parameters.
3. Finding Maximum: We determine the maximum of the two numbers and use it as the starting point for our search for LCM.
4. Loop to Find LCM: We increment the maximum value until it is divisible by both numbers.
5. Return LCM: Once the LCM is found, it is returned by the function.
6. Output: Display the calculated LCM.

• C

C

#include <stdio.h>

// Function to calculate LCM
int lcm_fun(int num1, int num2) {
    int max_div = (num1 > num2) ? num1 : num2;

    // Loop until we find the LCM
    while (1) {
        if (max_div % num1 == 0 && max_div % num2 == 0) {
            return max_div;
        }
        max_div++;
    }
}

int main() {
    // Input two numbers
    int num1 = 18, num2 = 12;

    // Call the LCM function
    printf("LCM of two numbers %d and %d is %d", num1, num2, lcm_fun(num1, num2));

    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

LCM of two numbers 18 and 12 is 36.

Time Complexity:

O(num1 * num2): In the worst case, this approach has a time complexity proportional to the product of the two numbers.

Space Complexity:

• O(1): It uses constant space.

LCM of two numbers in C using recursive function

• Recursive GCD Function: The GCD (Greatest Common Divisor) of two numbers is calculated using recursion.
   
• LCM Calculation: We use the formula LCM = (num1 * num2) / GCD(num1, num2) to calculate the LCM.
   
• Recursion Base Case: If the first number becomes zero, the second number is returned as the GCD.
   
• Recursive Call: Otherwise, the GCD function is called recursively with swapped parameters.
   
• Output: Display the calculated LCM using the recursive approach.

• C

C

#include <stdio.h>

// Recursive function to calculate GCD
int gcd(int num1, int num2) {
    if (num1 == 0) {
        return num2;
    }
    return gcd(num2 % num1, num1);
}

// Function to calculate LCM using GCD
int lcm_fun(int num1, int num2) {
    return (num1 * num2) / gcd(num1, num2);
}

int main() {
    // Input two numbers
    int num1 = 18, num2 = 12;

    // Call the LCM function
    printf("LCM of two numbers %d and %d is %d", num1, num2, lcm_fun(num1, num2));

    return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

LCM of two numbers 18 and 12 is 36.

Time Complexity:

O(log(max(num1, num2)): The time complexity for calculating the GCD is logarithmic.

Space Complexity:

• O(1): The space complexity is constant, as no extra memory is used beyond function calls.

Frequently Asked Questions 

How do you find the LCM of two numbers in C?

You can find the LCM of two numbers in C by identifying the greater of the two numbers and checking for the smallest number that is divisible by both. You can also use the formula LCM = (num1 * num2) / GCD(num1, num2).

What is the algorithm for LCM of two numbers?

To find the LCM, begin by calculating the GCD (Greatest Common Divisor) of the two numbers using the Euclidean algorithm. Then, use the formula LCM = (num1 * num2) / GCD(num1, num2) to compute the LCM efficiently.

Can I find the LCM without using GCD in C?

Yes, you can find the LCM without using GCD by checking for divisibility. Start with the greater of the two numbers and increment it until both numbers divide it evenly, at which point that number is the LCM.

What header files are required for the LCM program in C?

For a simple LCM program in C, you typically need the stdio.h header file for input/output operations. If you're using functions like clrscr() or getch(), you might also include conio.h, but it's not necessary for basic LCM logic. 

Conclusion

In this article, we discussed different methods to find the LCM of two numbers in C. Calculating the LCM is a fundamental mathematical concept that is useful in various applications. In C, you can compute the LCM using loops, GCD-based approaches, or recursive techniques for efficient and accurate results.