LCM of Two Numbers in C
In this article, we will learn how to write a C program to find the LCM of two numbers. LCM (Least Common Multiple) of two numbers is the smallest positive number that can be divided by both numbers without leaving a remainder. For example, the LCM of 15 and 25 is 75.
Algorithm to Find LCM in C
- Find the maximum of the two numbers and store them in a variable max.
- Run a loop and check if max is divisible by both numbers.
- if (max % x == 0 && max % y == 0)
- If the condition is true, it means that max is the LCM of the two numbers.
- If the condition is false, increment max by 1 and continue the loop to check the next number.
C Program To Find LCM of Two Numbers
C
// C program to find LCM of // two numbers #include <stdio.h> // Driver code int main() { int x = 15, y = 25, max; max = (x > y) ? x : y; // While loop to check if max variable // is divisible by x and y while (1) { if (max % x == 0 && max % y == 0) { printf("The LCM of %d and %d is %d.", x, y, max); break; } ++max; } return 0; } |
Output
The LCM of 15 and 25 is 75.
Complexity Analysis
- Time complexity: O(x*y)
- Auxiliary space: O(1)
LCM of Two Numbers using GCD
In mathematics, the LCM of two numbers is the product of two numbers divided by their GCD. So,
LCM(a, b) = (a x b) / GCD(a, b)
Refer to the article Program to Find GCD or HCF of Two Numbers to learn how to find the GCD of two numbers.
C Program To Find LCM of Two Numbers using GCD
C++
// C++ program to find LCM of two numbers #include <iostream> using namespace std; // Recursive function to return gcd of a and b long long gcd(long long int a, long long int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to return LCM of two numbers long long lcm(int a, int b) { return (a / gcd(a, b)) * b; } // Driver program to test above function int main() { int a = 15, b = 20; cout << "LCM of " << a << " and " << b << " is " << lcm(a, b); return 0; } |
Output
LCM of 15 and 20 is 60
Complexity Analysis
- Time complexity: O(log(min(a, b)))
- Auxiliary space: O(1)
Please refer to the complete article Program to find LCM of two numbers for more methods to find LCM of two numbers.
Contact Us