In this guide, we will analyze various patterns to find the GCD with methods in C++.
C++ Program to Find GCD
In C++, to get the greatest positive integer that divides two provided numbers without leaving any remainder, use the GCD (Greatest Common Divisor). It assists in simplifying fractions and resolving issues involving common factors. The GCD function in a program returns the greatest common factor between two input integers.
C++ provides multiple methods for calculating the GCD of two numbers. Some of them are described below.
Method 1: Find GCD Using Euclidean-Algorithm in C++
The “Euclidean Algorithm” is a widely used and reliable method for determining the GCD of two different numbers. It is based on the fact that the GCD for two integers remains unchanged if a smaller number(integer) is deducted from the larger one, and this approach goes on until any of the integers becomes zero.
Let’s have a look at the below example, here we are finding the (GCD) of two numbers using the Euclidean algorithm. First, include the required libraries:
using namespace std;
Here:
- “<iostream>” header file includes the input and output streams, which enables input and output operations.
- “using namespace std” is a directive that makes it easier to use names that come from the std namespace.
Then, declare the “find_GCD()” function which takes two integer parameters “value1” and “value2” respectively. Next, use the “if” statement to check the “value1” that will always be greater and equal to “value2”. After this, a “while” loop is used that continues to return value until the condition “value2 != 0” becomes false. Inside the “while” loop, “value1” is divided by “value2” and saves the result in the “remainder” variable.
The values of “value1” and “value2” are updated as “value1” becomes the current value of “value2”, and “value2” becomes the calculated “remainder”. The loop continues until the “value2” becomes 0, at that point the GCD has been found with the Euclidean algorithm. Finally, return “value1” to the “find_GCD” function.
if (value2 > value1) {
swap(value1, value2);
}
while (value2 != 0) {
int remainder = value1 % value2;
value1 = value2;
value2 = remainder;
}
return value1;
}
In the “main()” function, declared “num1” and num1” variables. Then, use the “cout” statement to get input from the users. Next, the “cin” object is used to read the entered integers from the standard input and save them in the “num1” and “num2” variables. After that, called the “find_GCD()” method that takes “num1” and “num2” as parameters, and stored the results in the “my_result” variable. Lastly, used the “cout” with the “<<” insertion operator to print the estimated GCD on the console:
int num1, num2;
cout << "Enter two numbers "<<endl;
cin >> num1 >> num2;
int my_result = find_GCD(num1, num2);
cout << "GCD of two integers using Euclidean Algorithm: " << my_result << endl;
return 0;
}
Output
Method 2: Find GCD Recursively in C++
Another method to calculate GCD in C++ is recursively using the if statement. Let’s check out the below-given simple program example in C++.
In the below code, define the “calculate_Gcd()” function to calculate the GCD of two numbers. It takes two integer parameters, “a” and “b”. It will check whether the “b” is equal to the “0”, then return the “a”. Otherwise, the “calculate_Gcd()” function recursively calls with parameters “b” and “a%b”:
using namespace std;
int calculate_Gcd(int a, int b)
{
if (b == 0)
return a;
return calculate_Gcd(b, a % b);
}
Next, declare the “num1” and “num2” variables inside the “main()” function. After this, use the “cout” statement to display the “Enter two numbers” message, then the “cin” object reads and saves the variables which are entered by the user. Moving forward, invoked the “calculate_Gcd()” function with input values “num1” and “num2”. Saved inside the “result” variable and used the “cout” to display the resultant value:
{
int num1, num2;
cout << "Enter two numbers: " <> num1 >> num2;
int result = calculate_Gcd(num1, num2);
cout << "GCD of two numbers using Recursive Method " << result << endl;
return 0;
}
Output
Method 3: Find GCD Using for Loop in C++
The below-given program used the “for” loop to discover the largest common divisor:
using namespace std;
int main() {
int value1, value2, gcd;
cout << "Enter two values of integer type"<> value1>> value2;
if ( value2 > value1) {
int temp = value2;
value2 = value1;
value1 = temp;
}
for (int i = 1; i <= value2; ++i) {
if (value1 % i == 0 && value2 % i ==0) {
gcd = i;
}
}
cout << "GCD of two values using for Loop: " << gcd;
return 0;
}
In the above code, first, declare three integer variables “value1”, “value2”, and “gcd” inside the “main()” function. Next, use the “cout” object to get the input values from the users. The user’s input values are saved in the “value1” and “value2” using the “>>” operator with the “cin” object. Then, use the “if” statement to check if the “value1” is “>” than “value2” by checking if the “temp” variable holds the “value2” and then assign it to “value1” to “value2” and “temp” to “value1”. After this, the “for” loop iterates until the inside “if” condition is satisfied. Lastly, use the “cout” statement to print the result. As follows:
You have learned about the C++ programming methods for finding GCD.
Conclusion
The GCD is an important concept of mathematics that helps users to determine the largest positive integer that divides both numbers without any remainder behind. Multiple methods are used to find the GCD in C++, such as the “Euclidean Algorithm”, “recursive”, and “for” loop. In this guide, we have illustrated the C++ programming methods for finding GCD.
