The highest common factor is also known as GCD (Greatest common divisor). GCD is the largest possible integer which can be divided by the given numbers without a remainder.
Note: GCD is also known as HCF(Highest Common Factor).
LCM, lowest common multiple is the least possible integer which can be divided by the given numbers without a remainder.
In the example given below, we will take two numbers and find their GCD and LCM.
Logic:
For GCD:
We will take a number, check if it is perfectly divisible by both numbers. We store the value in a variable, and then, print the variable.
For LCM:
We use a formula here,
LCM = Num1*Num2/GCD
Algorithm:
- Take two number’s as input.
- Check if the given numbers are divisible by any number less than the number itself using for loop.
- If yes, then store it (in gcd) and continue ahead.
- After termination of the loop, the last updated value in gcd will be GCD.
- To find LCM of the numbers apply the formula for lcm.
- Now, Print the GCD and LCM
Code:
#include<iostream> using namespace std; int main() { int fnum,snum,gcd,lcm; cout<<"Enter first number"; cin>>fnum; cout<<"\nEnter second number"; cin>>snum; //find factors of both numbers for(int i=1;i<=fnum && i<=snum;i++) { if(fnum%i==0 && snum%i==0) gcd=i; } //find lcm of both numbers lcm = fnum*snum/gcd; cout<<"\n GCD of given numbers is:"<<gcd; cout<<"\n LCM of given numbers is:"<<lcm; return 0; }
Output:
Enter first number 10 Enter second number 5 GCD of given numbers is:5 LCM of given numbers is:10
Report Error/ Suggestion