# Finding the Greatest Common Divisor (GCD) of Two Numbers using C++

In this article, we will learn how to find the GCD of two numbers using for loop, while loop, recursion, and nested if else statement in C++.

The greatest common divisor (GCD) of two numbers is the largest positive integer that divides both numbers without a remainder. It is also known as the “highest common factor” (HCF) of the numbers. The GCD can be found using the Euclidean algorithm or the more efficient binary GCD algorithm.

In this article, we will learn how to find the GCF of two numbers using the following methods in C++:

Let’s look at an example of each of these methods:

**Using For Loop**

Here is an example of a function in C++ that finds the GCD of two numbers using a for loop:

#include <iostream>using namespace std;
int main() { int num1, num2, gcd; cout << "Enter two numbers: "; cin >> num1 >> num2;
// swapping variables num1 and num2 if num2>num1 if ( num2 > num1) { int temp = num2; num2 = num1; num1 = temp; } for (int i = 1; i <= num2; ++i) { if (num1 % i == 0 && num2 % i ==0) { gcd = i; } }
cout << "GCD: " << gcd;
return 0;}

**Output:**

The above program swaps the two input numbers **nujm1** and **num2** if **num2** is greater than **num1** before the for loop. This is just to ensure that the for loop iterates over the smaller of the two numbers, making the calculation more efficient.

The for loop starts at 1 and goes up to the smaller of the two input numbers. It checks if the current number **i**, is a divisor of both input numbers, and if so it sets that number as the current greatest common divisor. After the loop ends, the final value of **gcd** is the GCD of the two input numbers. The program then outputs the result.

**Must Read:** Understanding for loop in C++

**Using While Loop**

Here is an example of a function in C++ that finds the GCD of two numbers using a while loop:

#include <iostream>using namespace std;
int main() { int num1, num2, remainder; cout << "Enter two numbers: "; cin >> num1 >> num2;
while (num2 != 0) { remainder = num1 % num2; num1 = num2; num2 = remainder; }
cout << "GCD = " << num1;
return 0;}

**Output**

The program uses a while loop and executes the code inside the loop as long as the value of **num2** is not equal to 0. Inside the loop, the program calculates the remainder of **num1 **divided by **num2** and assigns the value to the remainder variable. The program then assigns the value of **num2** to **num1** and the value of **remainder** to **num2**.

The loop continues to execute until **num2** becomes 0. At this point, the value of **num1** is the GCD of the two input numbers. The program then outputs the result.

**Must Read:** Difference between While and Do while Loop in C++

**Using Recursion**

Here is an example of a function in C++ that finds the GCD of two numbers using recursion:

#include <iostream>using namespace std;
int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b);}
int main() { int a, b; cout <<"Enter two numbers:"; cin >> a >> b; cout << "GCD of " << a << " and " << b << " is: " << gcd(a, b) << endl; return 0;}

**Output:**

This program takes two integers as input from the user, and finds the greatest common divisor (GCD) of these two numbers using recursion. The **gcd()** function uses the Euclidean algorithm to find the GCD. This function recursively calls itself with the two numbers swapped (i.e., **gcd(b, a % b)**) until the remainder is zero, at which point the larger number is returned as the GCD.

**Must Read:** Recursion in C++

**Using Nested If Else**

Here is an example of a function in C++ that finds the GCD of two numbers using a nested if-else if-else statement:

#include <iostream>using namespace std;
int gcd(int a, int b) { if (a == 0) return b; else if (b == 0) return a; else { if (a > b) return gcd(a - b, b); else return gcd(a, b - a); }}
int main() { int a, b; cout << "Enter two numbers: "; cin >> a >> b; cout << "GCD of " << a << " and " << b << " is: " << gcd(a, b) << endl; return 0;}

**Output:**

This program takes two integers as input from the user, and finds the greatest common divisor (GCD) of these two numbers using nested if-else statements. The **gcd()** function uses the subtraction-based algorithm to find the GCD, which states that the GCD of two numbers is the same as the GCD of the difference between the larger number and the smaller number and the smaller number.

This function recursively calls itself with the two numbers swapped (i.e., **gcd(a, b – a)**) until one of the number becomes zero, at which point the non-zero number is returned as the GCD.

**Must Read:** if-else in C++

**Conclusion**

Hope this article was helpful for you to understand how to find the greatest common divisor of two numbers in C++. If you want to learn more about C++ and solidify your basics, you can explore our articles on C++.

**Contributed By: Prerna Singh**

**About the Author**

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio