Program to Find the Greatest Common Divisor (GCD) in C++

Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCD of 36 and 60 is 12.

We will explore three different methods to find the GCD of two numbers using C++ programming.

Method 1: Using Euclidean Algorithm

The Euclidean algorithm repeatedly replaces the larger number with its remainder when divided by the smaller number until the remainder becomes zero.

#include <iostream>
using namespace std;

int findGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1, num2;
    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;
    
    cout << "GCD of " << num1 << " and " << num2 << " is " << findGCD(num1, num2);
    return 0;
}
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12

Method 2: Using Recursion

In this method, we use recursion to apply the Euclidean algorithm.

#include <iostream>
using namespace std;

int findGCD(int a, int b) {
    if (b == 0)
        return a;
    return findGCD(b, a % b);
}

int main() {
    int num1, num2;
    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;
    
    cout << "GCD of " << num1 << " and " << num2 << " is " << findGCD(num1, num2);
    return 0;
}
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12

Method 3: Using Iteration

In this method, we iterate from the smaller number down to 1 and find the largest number that divides both inputs.

#include <iostream>
using namespace std;

int findGCD(int a, int b) {
    int gcd = 1;
    for (int i = 1; i <= min(a, b); i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }
    return gcd;
}

int main() {
    int num1, num2;
    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;
    
    cout << "GCD of " << num1 << " and " << num2 << " is " << findGCD(num1, num2);
    return 0;
}
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12