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

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

Updated on Aug 5, 2024 11:08 IST

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;}Copy code```

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;}Copy code```

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.

### 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;}Copy code```

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.

### 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;}Copy code```

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.