WAP to calculate hcf and lcm of two numbers
Objective
Write a C++ program to calculate the HCF and LCM of two numbers.
Algorithm / Approach
- Read two numbers
aandb. - Determine the greater (
gr) and lower (low) of the two using ternary operators. - Start a
while (low != 0)loop. - Calculate the remainder:
temp = gr % low. - Shift variables:
gr = lowandlow = temp. - The HCF is the final value of
gr. - Calculate LCM using the mathematical formula:
(a * b) / HCF.
main.cpp
#include<iostream>
using namespace std;
int main() {
int a, b, gr, lcm, low, temp;
cout<<"Enter two Number : ";
cin>>a>>b;
gr =(a >= b)?a:b;
low =(a < b)?a:b;
while(low!=0) {
temp = gr % low;
gr = low;
low = temp;
}
cout<<"HCF = "<< gr<< endl;
lcm = (a*b)/gr;
cout<<"LCM = "<< lcm<< endl;
return 0;
}Expected Output
Enter two Number : 6 10 HCF = 2 LCM = 30
Explanation of the Program
- This program uses the Euclidean Algorithm to calculate the Highest Common Factor (HCF).
- The algorithm repeatedly replaces the larger number with the remainder of dividing the larger number by the smaller number until the remainder is 0. Once you have the HCF, calculating the LCM is a simple math equation.
Complexity
Time Complexity
O(log(min(a,b)))
Space Complexity
O(1)
