LCM of Two Numbers in C

Problem Description

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.

Problem Solution

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

Method 1: LCM of Two Numbers in C using While Loop

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

Program/Source Code

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

Program Explanation

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:

Subscribe Now: C Programs Newsletter | Important Subjects Newsletters

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.

Runtime Test Cases

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.

Method 2: LCM of Two Numbers using Recursion

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

Program/Source Code

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.

```
}
```

Program Explanation

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.

Runtime Test Cases

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.

Method 3: C Program to Find LCM of Two Numbers using GCD

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

Program/Source Code

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

Program Explanation

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.

Runtime Test Cases

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

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Find GCD of Two Numbers using Recursion

» Next - C Program to Find Sum of Series 1^2 + 2^2 + …. + n^2

Related Posts:

Check C Books
Practice BCA MCQs
Apply for Computer Science Internship
Apply for C Internship
Practice Computer Science MCQs

Recommended Articles: