LCM of Two Numbers in C

LCM stands for Least Common Multiple. It is the smallest positive integer that is divisible by two or more given integers. In other words, it is the smallest number that can be divided evenly by all of the given numbers.

For example, the LCM of 7 and 35 is 35. This is because 35 is the smallest number that is divisible by both 7 and 35.

Before reading this article, you should read the following C Programming topics:

• Operators in C
• Do while loop in C
• if-else Statement in C

Algorithm to find LCM of two numbers in C

To find the LCM of two numbers in C, we will assume the two numbers are num1 and num2 and that they are positive integers. We will use the following approach:

START

Step 1: Initialize two variables for num1(7) and num2(35).

Step 2: Find and store the maximum of num1 and num2 to a separate variable, ‘max’(35).

Step 3: If max is divisible by $num1($35 % 7 == 0?$)$ and $num2($35 % 35 == 0?$)$, max is the $LCM(35)$, hence print it.

Step 4: If not divisible, then increment max by 1, and go to step 3 until a number has been printed. Repeat the process of 3->4->3 until a max value is found that satisfies the constraints.

STOP

LCM of two numbers in C using while loop

Now that we have studied the algorithm let us implement the same using a while loop.

Explanation :

The following code assigns to the variable ‘max’ the number that’s the largest between num1 and num2 using the ternary operator.

A ternary operator has been used in the above line, which has the syntax of condition.

value_if_true : value_if_false

while(1) is an infinite loop until it comes across an explicit break statement and it is used to find the LCM of two numbers in C as we must repeatedly check whether or not max is divisible by the two numbers. Once such a number is found, we print the number and break from the loop.

Code:

Output :

Time Complexity:

O(X), where x = num1 * num2 Our while loop runs till res reaches LCM, i.e. 35.

For example, in this case both 7 and 5 are prime numbers, hence LCM will be the product of the two numbers, therefore loop will run till 35, and stop there as it suits all criteria, hence the time complexity is O(x), where $x = num1 * num2$.

LCM of two numbers in C Using GCD

The relationship between GCD and LCM is as illustrated below:

Explanation:

To find LCM of two numbers in C:

• Ask user to enter two variables.
• Using a for loop, find a number, starting from 1 that’s smaller than num1 and num2 that satisfies the condition: num1 % i == 0 and num2 % i == 0.
• Largest ‘i’ in the for loop that suits the above mentioned criteria, is the GCD.
• Find LCM by using the formula given, i.e. $\frac{(num1*num2)}{gcd}$ .

Code:

Output:

Time Complexity:

Here the loop runs till the minimum of both the numbers of the input and we find the greatest common factor for both the numbers and store it in a variable called gcd and hence worst-case time complexity = O(min(num1,num2)).

GCD Optimized We can also use Euclid's algorithm to calculate the GCD of two numbers in an optimized manner.

Code:

Output:

Time Complexity:

Since we are using Euclid's algorithm to find the GCD of two numbers, the final time complexity is O(log(max(num1, num2))).

LCM of two numbers in C using function

In order for code to be reused, we can put the while loop in a function and call it so as to find the LCM.

Explanation:

The same algorithm is followed for the while loop as in the LCM program in C using while, except this time, we have a function call as:

Functions have the following advantages –

1. They increase the readability of code.
2. They improve code reusability; rather than developing the same code from scratch, the same function can be used in any program.
3. Using functions makes debugging the code easier because faults are more easily traced.

Code:

Output:

Time Complexity:

O(X), where x = num1 * num2

Our while loop runs till res reaches LCM, i.e. 35.

For example, in this case both 7 and 5 are prime numbers, hence LCM will be the product of the two numbers, therefore loop will run till 35, and stop there as it suits all criteria, hence the time complexity is O(x) where x = num1 * num2.

LCM of two numbers in C using recursive function

A recursive function is a routine that calls itself explicitly or indirectly in programming terms. Certain problems can be solved quickly using the recursive algorithm.

Explanation:

The same algorithm is followed for the if block as in the lcm program in c using while, except this time, instead of using an infinite while loop, we have a function call as displayed below:

This function is called again in the else block if the lcm is not found and hence, it keeps running until an lcm is found which is why we do not require an infinite while loop in the lcm program in c using functions.

Code:

Output:

Learn more about the most favored programming language - C programming. We have structured our C tutorial for beginners, which gradually goes to an advanced level.

We have integrated real-world examples wherever possible for a deeper understanding.

See More

GCD of Two Numbers in C