LCM of Two Numbers Using GCD
An efficient solution is based on the below formula for LCM of two numbers ‘a’ and ‘b’.
a x b = LCM(a, b) * GCD (a, b) LCM(a, b) = (a x b) / GCD(a, b)
We have discussed the function to find the GCD of two numbers. Using GCD, we can find LCM.
C++ Program to Find LCM Using GCD
C++
// C++ program to find LCM// of two numbers#include <iostream>using namespace std;// Recursive function to return// gcd of a and blong 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 numberslong long lcm(int a, int b) { return (a / gcd(a, b)) * b; }// Driver codeint main(){ int a = 15, b = 20; cout << "LCM of " << a << " and " << b << " is " << lcm(a, b); return 0;} |
Complexity Analysis
- Time Complexity: O(log(min(a,b))
- Auxiliary Space: O(log(min(a,b))
Refer to the complete article Program to find LCM of two numbers for more details.
Related Articles
C++ Program To Find LCM of Two Numbers
LCM (Least Common Multiple) of two numbers is the smallest number that is divisible by both numbers. For example, the LCM of 15 and 20 is 60, and the LCM of 15 and 25 is 75. In this article, we will learn to write a C++ program to find the LCM of two numbers.
We can find the LCM of two numbers in C++ using two methods: