Here is a C++ Program to find LCM and GCD of two Numbers. In this C++ program we will learn about finding least common multiple(LCM) of two numbers. The LCM of two integers X and Y, denoted by LCM (a, b), is the smallest positive integer that is divisible by both a and b. Here, we will discuss about two ways to find LCM of two numbers.
C++ Program to find LCM of two numbers
#include <iostream>
using namespace std;
// Function to find LCM
int getLCM(int a, int b) {
int max;
// Find maximum of a and b
max = (a > b) ? a : b;
do {
if (max % a == 0 && max % b == 0) {
return max;
} else {
max++;
}
} while (true);
}
int main() {
int x, y;
cout << "Enter two integers\n";
cin >> x >> y;
cout << "LCM = " << getLCM(x, y);
return 0;
}
Output
Enter two integers 6 15 LCM = 30
In this program, we first take two integers as input from user and store it in variable x and y. Then we call getLCM function by passing x and y as parameters. Inside getLCM function, we first find the maximum of a and b and store it in variable max. Now, we are trying to find smallest number greater than both a and b which is divisible by both a and b. Using a do while, we are testing every number greater than max till we find LCM.
C++ Program to find LCM by Finding GCD First
The highest common factor(HCF) of two or more integers, is the largest positive integer that divides the numbers without a remainder. HCF is also known as greatest common
divisor(GCD) or greatest common factor(GCF).
Here is the relationship between LCM and HCF of two numbers.
If we know LCM or HCF of two numbers, then we can find the other one using above equation.
#include <iostream>
using namespace std;
// Function to find LCM
int getLCM(int a, int b) {
int max;
// Find maximum of a and b
max = (a > b) ? a : b;
do {
if (max % a == 0 && max % b == 0) {
return max;
} else {
max++;
}
} while (true);
}
int main() {
int x, y;
cout << "Enter two integers\n";
cin >> x >> y;
cout << "LCM = " << getLCM(x, y);
return 0;
}
Output
Enter two integers 6 15 LCM = 30
In this program, we first take two integers as input from user and store it in variable x and y. To find LCM of two number, we will first find HCF of two number and use above equation to find the LCM. We defined two function "getLcm" and "getGcd" to calculate LCM and GCD(HCF) of two numbers respectively. getLcm function internally calls getGcd function to get the HCF of two numbers and then use above equation to find LCM.
Recommended Posts