WAP to Calculate HCF and LCM of two Number
Objective
Write a C++ program to calculate HCF and LCM using functions.
Algorithm / Approach
- Define a function
hcf(int a, int b)that uses a while loop to find the Highest Common Factor. - Define a function
lcm(int a, int b)that calls the HCF function to calculate(a * b) / hcf(a,b). - Call both from
main().
main.cpp
#include<iostream>
using namespace std;
int lcm(int , int);
int hcf(int , int);
int main( ) {
int a,b;
cout<<"Enter two Number : ";
cin>>a>>b;
int lc=lcm(a,b);
int hc =(a>b)?hcf(a,b):hcf(b,a);
cout<<"LCM = "<< lc<< endl;
cout<<"HCF = "<< hc<< endl;
return 0;
}
int lcm(int a, int b) {
int res = a*b/hcf(a,b);
return res;
}
int hcf(int a, int b) {
int rem;
while( b != 0) {
rem = a%b;
a = b;
b = rem;
}
return a;
}Expected Output
Enter two Number : 15 50 LCM = 150 HCF = 5
Explanation of the Program
- Functions can call other functions!
- Our
lcm()function relies on the mathematical fact that LCM = (A * B) / HCF. Instead of reinventing the wheel, the LCM function simply calls the HCF function to do the heavy lifting.
Complexity
Time Complexity
O(log(min(a,b)))
Space Complexity
O(1)
