C++ gcd function: In the previous article, we have discussed about C++ Program to Find Factorial. Let us learn how to find GCD in C++ Program.
Methods to find HCF/GCD of two numbers in c++
In this article, we will discuss different methods in c++ for calculating the GCD/HCF of two numbers. The list of methods that we will discuss is given below:-
- Using loop and if statement
- Using Recursion
- Using recursion with the modulo(%) operator
- Using inbuilt function
First of all, let understand what a GCD/HCF is. GCD or HCF of two numbers is the largest number that divides both of them. For example, GCD of 36 and 60 will be equal to 12 because 12 is the largest num, ber that divides both 36 and 60.
Method 1-Using loop and if statement
The idea here is that we will find the common divisor of two numbers starting from 1 and then return the largest divisor. Let write the code for this.
#include <iostream> using namespace std; int main() { int num1=36, num2=60, i, gcd; for(i=1; i <= num1 && i <= num2; i++) { if(num1%i==0 && num2%i==0) gcd = i; } cout<<"GCD of two numbers "<<num1<<" and "<<num2<<" is "<<gcd; return 0; }
Output
GCD of two numbers 36 and 60 is 12
Method 2- Using Recursion
Here idea is that the GCD of two numbers doesn’t change if a smaller number is subtracted from a bigger number. So we use this idea with recursion and find the gcd of two numbers. Let’s write the code for this.
#include <iostream> using namespace std; int gcd_of_number(int num1, int num2) { if (num1 == 0) return num2; if (num2 == 0) return num1; if (num1 == num2) return num1; if (num1 > num2) return gcd_of_number(num1-num2, num2); return gcd_of_number(num1,num2-num1); } int main() { int num1=36, num2=60, i, gcd; cout<<"GCD of two numbers "<<num1<<" and "<<num2<<" is "<<gcd_of_number(num1,num2); return 0; }
Output
GCD of two numbers 36 and 60 is 12
Method 3-Using recursion with the modulo(%) operator
Here the idea is the same as the above method but here we use the modulo operator where we are able to write the same idea in fewer lines. Let’s write the code for this.
#include <iostream> using namespace std; int gcd_of_number(int num1, int num2) { if (num2 == 0) return num1; return gcd_of_number(num2, num1 % num2); } int main() { int num1=36, num2=60, i, gcd; cout<<"GCD of two numbers "<<num1<<" and "<<num2<<" is "<<gcd_of_number(num1,num2); return 0; }
Output
GCD of two numbers 36 and 60 is 12
Method 4-Using inbuilt function
C++ has the built-in function for calculating GCD. This function returns 0 if both m and n are zero, else returns the gcd of two numbers. Let’s write code for this.
#include <bits/stdc++.h> using namespace std; int main() { int num1=36, num2=60, i, gcd; cout<<"GCD of two numbers "<<num1<<" and "<<num2<<" is "<<__gcd(num1,num2); return 0; }
Output
GCD of two numbers 36 and 60 is 12
So these are the methods to find GCD/HCF of two numbers in c++.