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

3 mins read802 Views Comment

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++:

Using For Loop
Using While Loop
Using Recursion
Using Nested If Else

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.

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;
}
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.

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;
}
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.

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

Shiksha Online

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

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

Using For Loop

Using While Loop

Using Recursion

Using Nested If Else

Conclusion

Top Picks & New Arrivals