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