Write a C program to find the LCM of two numbers.

**What is LCM (Least Common Multiple)?**

LCM stands for Least Common Multiple. It is a method to find the lowest common multiple between the two numbers.

LCM of two numbers is the lowest possible number that is divisible by both numbers.

**Examples:** LCM(10,15) = 30, LCM(18,26) = 234.

1. Take two numbers as input.

2. Find the maximum of the two numbers.

3. If the maximum is completely divisible by both the numbers return the maximum as output.

4. Else keep on increasing the maximum one by one until it is completely divisible by both the numbers.

5. Finally return the new value of the maximum.

There are several ways to find the LCM of two numbers in C language. Let’s look at the three different techniques to write a C program to calculate the LCM of two numbers.

- LCM of Two Numbers in C using While Loop
- LCM of Two Numbers in C using Recursion
- LCM of Two Numbers in C using GCD

In this approach, we find the LCM of two numbers using a while-loop

Here is the source code of the C program to find the LCM of two numbers using while loop. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/* * C program to find LCM of two numbers */ #include<stdio.h> void main() { int a, b, max; printf("Enter the two numbers : "); scanf("%d %d", &a, &b); max = (a > b) ? a : b; // maximum number between a and b is stored in max while (max % a != 0 || max % b != 0) { max++; } printf("The LCM of %d and %d is %d.", a, b, max); }

1. Take the two numbers **a** and **b** as input.

2. Take another variable **max** and store the maximum of two numbers into it.

3. Run a while loop until **max** is completely divisible by both the numbers a and b.

4. Increment the value of **max** by 1, each time while-loop is entered.

5. When the condition in the while-loop becomes false come out of the loop and print the value of **max**, it will be the LCM of the two numbers.

**Example:**

- Consider an example, let the two numbers be
**a=2**and**b=5**. So, the value of**max**will be the maximum of these two numbers that is,**max=5**. - Now, check the condition in while-loop
**(5 % 2 != 0 || 5%5!=0)**, since the 1^{st}condition inside while-loop is true, we enter the while loop and increment**max**value by 1, i.e.,**max=6**. - Again check the conditions in the while-loop
**(6% 2 != 0 || 6%5!=0)**, now the 1^{st}condition is false as**(6%2==0)**but the 2^{nd}condition is true hence, we again increment value of**max**by 1 i.e.,**max=7**. - This loop continues until both the conditions become false. Let us check for
**max = 10**.**(10 % 2 != 0 || 10%5!=0)**, here both the conditions become false and hence we come out of the while loop and print the LCM as**max**i.e., 10.

**Time Complexity: O(n)**

The above program to find the LCM of two numbers has a time complexity of O(n), because we are using a while loop that runs with (LCM – maximum of two numbers) times.

**Space Complexity: O(1)**

In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

**Testcase 1:** The numbers entered by the user to calculate lcm in this case are 2 and 5.

Enter the two numbers: 2 5 The LCM of 2 and 5 is 10.

**Testcase 2:** The numbers entered by the user to calculate lcm are 12 and 15.

Enter the two numbers: 12 15 The LCM of 12 and 15 is 60.

In this approach, lcm() function is used to find the LCM of two numbers using recursion.

Here is the source code of the C program to find the LCM of two numbers using recursion. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C Program to Find LCM of a Number using Recursion`

`*/`

`#include <stdio.h>`

int lcm(int, int);

int main()

`{`

int a, b, result;

printf("Enter two numbers: ");

scanf("%d%d", &a, &b);

result = lcm(a, b); //call the function lcm recursively.

printf("The LCM of %d and %d is %d\n", a, b, result);

return 0;

`}`

int lcm(int a, int b)

`{`

static int common = 1;

if (common % a == 0 && common % b == 0)

`{`

return common;

`}`

`common++;`

lcm(a, b); //call the function lcm recursively.

`}`

1. In this C program, we are reading the two integer numbers using ‘**a**’ and ‘**b**’ variables respectively.

2. The **lcm()** function is used to find the LCM of a number using recursion.

3. Assign the value of the ‘**common**’ variable as 1.

4. If the condition statement is used to check the modulus of the ‘**common**’ variable divided by the value of ‘**a**’ and also divided by the value of ‘**b**’ is equal to 0 or not.

5. If the condition is true, then execute the statement and return the ‘**common**’ value. 6. Print the LCM of a number using the printf statement.

**Example:**

- Consider the two numbers
**a**and**b**are 2 and 3 respectively. - In the main function
**lcm()**function is called. Inside the**lcm()**function value of**common**is assigned to 1. - Now, check the if condition
**if (common % a == 0 && common % b == 0)**so, for**common = 1**, this condition becomes false and outside the if condition**common**value is incremented by 1 and again**lcm()**function is being called. - Now, the
**common**value becomes 2, this process is repeated till the**common**value becomes 6. - When the value of
**common**becomes 6, if the condition becomes true as it is divisible by both**a=2**and**b=3**, it returns 6 to the main function which gets stored in the**result**variable. - Now, the printf statement prints LCM as 6.

**Time Complexity: O(n)**

The above program to find the LCM of two numbers has a time complexity of O(n), because the recursion is called many times until the LCM is found, where n = LCM of the two numbers.

Since the LCM is calculated using the common variable and the common variable starts from 1.

**Space Complexity: O(1)**

In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

**Testcase 1:** The numbers entered by the user to find the lcm in this case are 2 and 3.

Enter the two numbers: 2 3 The LCM of 2 and 3 is 6.

**Testcase 2:** The numbers entered by the user to calculate lcm are 12 and 15.

Enter the two numbers: 12 15 The LCM of 12 and 15 is 60.

In this approach, we find the LCM of two numbers using GCD (Greatest Common Divisor).

Here is the source code of the C program to find the LCM of two numbers using GCD. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

/* * C program to find the LCM of two numbers using GCD */ #include<stdio.h> void main() { int num1, num2, gcd, lcm, remainder, numerator, denominator; printf("Enter two numbers\n"); scanf("%d %d", &num1, &num2); if (num1 > num2) { numerator = num1; denominator = num2; } else { numerator = num2; denominator = num1; } remainder = numerator % denominator; while (remainder != 0) { numerator = denominator; denominator = remainder; remainder = numerator % denominator; } gcd = denominator; lcm = (num1 * num2) / gcd; printf("LCM of %d and %d = %d\n", num1, num2, lcm); }

1. In this C program, we are reading the two integer numbers.

2. First, few compare the two numbers. Store the greater number in the **numerator** and the smaller number in the **denominator**.

3. Run the while loop until the **remainder** becomes ‘0’.

4. Inside the while loop keep on dividing the **numerator** by **denominator** and store the value in the **remainder** variable.

5. When the value of the **remainder** variable becomes ‘0’ come out of the loop and store the value of the **denominator** in the **gcd** variable.

6. Now, calculate the **lcm** by the formula **lcm = (num1 * num2) / gcd** and then print the value of **lcm**.

**Example:**

- Consider, the two numbers 12 and 15, first find the greater of the two numbers and store the greater in the
**numerator**and smaller in the**denominator**i.e.,**numerator=15**and**denominator=12**. - Divide the
**numerator**by the**denominator**and store the value in the**remainder**variable i.e.,**remainder = 15%12 = 3**. - Now, enter the while loop and check if the
**remainder**value is ‘0’ or not. - Now, assign the value of the
**denominator**to the**numerator**and the value of the**remainder**to the numerator i.e.,**numerator=12**and**denominator=3**then calculate the**remainder**of the two variables i.e.,**remainder=12%3=0**. - Now, check the while loop condition again, this time
**remainder = 0**, therefore come out of the loop and store the value of the**denominator**in**gcd**i.e.,**gcd = 3**. - Now, using the formula of
**lcm (lcm = (num1 * num2) / gcd)**calculate**lcm**i.e.,**lcm = (12*15)/3 = (180/3) = 60**. - Print the
**lcm**of the two numbers.

**Time Complexity: O(log(min(a,b)))**

The above program for finding LCM of two numbers has a time complexity of O(log(min(a,b))), as the while loop runs for number of times the numerator is divided by the denominator.

**Space Complexity: O(1)**

In the above program, space complexity is O(1) as no extra variable has been taken to store the values in the memory. All the variables initialized takes a constant O(1) space.

**Testcase 1:** The numbers entered by the user to calculate lcm in this case are 2 and 3.

Enter the two numbers: 12 15 The LCM of 12 and 15 is 60.

**Testcase 2:** In this case, the numbers entered by the user to find lcm are 12 and 15.

Enter the two numbers: 7 2 The LCM of 7 and 2 is 14.

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

**Related Posts:**

- Practice Computer Science MCQs
- Practice BCA MCQs
- Check Computer Science Books
- Apply for C Internship
- Watch Advanced C Programming Videos