C++ Program to Find GCD of Two Numbers

C++ Program to Find GCD of Two Numbers

By /

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder. For example, the GCD of 12 and 18 is 6. Finding the GCD is a fundamental concept in mathematics and computer programming, with applications in simplifying fractions, solving number theory problems, and designing algorithms. In C++, there are multiple ways to calculate the GCD, ranging from simple loops to efficient algorithms like the Euclidean method. This article will walk you through beginner-friendly programs to find the GCD of two numbers in C++.

Program 1: Using a Simple Loop

The easiest way to find the GCD is by checking every number from 1 to the smaller of the two given numbers.

#include <iostream>

using namespace std;

int main() {

    int a, b, gcd = 1;

    cout << "Enter two numbers: " << endl;
    cin >> a >> b;

    int minNum = (a < b) ? a : b;

    for(int i = 1; i <= minNum; i++) {

        if(a % i == 0 && b % i == 0) {
            gcd = i;
        }

    }

    cout << "GCD of " << a << " and " << b << " is " << gcd << endl;

    return 0;

}

In this program, we first find the smaller of the two numbers because the GCD cannot be larger than that. The loop checks each number from 1 to the smaller number. If a number divides both a and b evenly, it is stored as the current GCD. This method is very simple and helps beginners understand the concept of divisibility, though it is not the most efficient for large numbers.

Program 2: Using the Euclidean Algorithm (Subtraction Method)

A more efficient method for finding GCD is the Euclidean algorithm, which repeatedly subtracts the smaller number from the larger one until both numbers are equal.

#include <iostream>

using namespace std;

int main() {

    int a, b;

    cout << "Enter two numbers: " << endl;
    cin >> a >> b;

    while(a != b) {

        if(a > b)
            a -= b;
        else
            b -= a;

    }

    cout << "GCD of the two numbers is " << a << endl;

    return 0;

}

Here, the program uses a while loop that continues until a equals b. In each step, the larger number is reduced by the smaller one. When the loop ends, the value of a (or b) is the GCD. This method is much faster than the simple loop, especially for larger numbers, and introduces beginners to a classic and important algorithm in programming.

Program 3: Using the Euclidean Algorithm (Modulo Method)

An even more optimized version of the Euclidean algorithm uses the modulo operator, which is widely used in professional programming.

#include <iostream>

using namespace std;

int main() {

    int a, b;

    cout << "Enter two numbers: " << endl;
    cin >> a >> b;

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

    cout << "GCD of the two numbers is " << a << endl;

    return 0;

}

In this program, the modulo operator % finds the remainder when a is divided by b. The algorithm continues until b becomes zero. At that point, a holds the GCD. This method is extremely efficient, works for very large numbers, and is a standard approach used in real-world programming. Beginners can learn how modulo operations can simplify repetitive calculations.

Program 4: Using the Built-in std::gcd() Function (C++17 and Later)

Modern C++ makes calculating the GCD even easier with the built-in std::gcd() function from the <numeric> library. This method is simple, efficient, and recommended for real-world programs.

#include <iostream>
#include <numeric> // Required for std::gcd

using namespace std;

int main() {

    int a, b;

    cout << "Enter two numbers: " << endl;
    cin >> a >> b;

    int result = gcd(a, b); // std::gcd computes the greatest common divisor

    cout << "GCD of " << a << " and " << b << " is " << result << endl;

    return 0;

}

In this program, the gcd() function directly returns the greatest common divisor of a and b. You don’t need to write loops or implement the Euclidean algorithm yourself. For beginners, this method is a great way to see how modern C++ libraries simplify common tasks while still producing accurate and efficient results.

Using std::gcd() is the preferred approach in C++17 and later because it is concise, easy to read, and works efficiently with very large numbers. While learning loops or the Euclidean algorithm is important for understanding the logic, in professional or practical coding, std::gcd() saves time and reduces the chance of errors.

Program 5: Finding GCD of Multiple Numbers

You are not limited to just two numbers. By applying the GCD function iteratively, you can find the GCD of three or more numbers. This approach is helpful for real-world scenarios where you need the GCD of several values.

#include <iostream>
#include <numeric> // Required for std::gcd
#include <vector>

using namespace std;

int main() {

    vector<int> numbers {24, 36, 60}; // Example numbers
    int result = numbers[0];

    for(size_t i = 1; i < numbers.size(); i++) {
        result = gcd(result, numbers[i]); // Iteratively calculate GCD
    }

    cout << "GCD of the numbers is " << result << endl;

    return 0;

}

In this program, we store multiple numbers in a vector. Starting with the first number, we iteratively compute the GCD with each subsequent number. By the end of the loop, result holds the GCD of all numbers. Beginners can see how std::gcd() can be extended beyond two numbers, making it a versatile and powerful tool in C++ programming.

Calculating the GCD of multiple numbers is common in problems involving fractions, ratios, and optimization algorithms. By learning to apply std::gcd() iteratively, beginners can handle arrays or lists of numbers efficiently, not just pairs.

Program 6: Using a Custom Function to Find GCD

You can define your own function to calculate the GCD. This makes your code cleaner and allows you to find the GCD of multiple numbers by calling the function repeatedly.

#include <iostream>

using namespace std;

// Custom function to find GCD of two numbers using Euclidean algorithm
int findGCD(int a, int b) {

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

    return a;

}

// Function to find GCD of multiple numbers in an array
int findGCDofArray(int arr[], int n) {

    int result = arr[0];

    for(int i = 1; i < n; i++) {
        result = findGCD(result, arr[i]);
    }

    return result;

}

int main() {

    int numbers[] {48, 180, 240};
    int n = sizeof(numbers) / sizeof(numbers[0]);

    int gcdResult = findGCDofArray(numbers, n);

    cout << "GCD of the numbers is " << gcdResult << endl;

    return 0;

}

In this program, we first define findGCD(int a, int b), which uses the Euclidean algorithm to calculate the GCD of two numbers. Then we define findGCDofArray(int arr[], int n) to calculate the GCD of an array of numbers by repeatedly calling findGCD.

This approach is highly reusable because you can now pass any pair or list of numbers to your function. Beginners can see how functions make code modular, readable, and easier to maintain.

Frequently Asked Questions (FAQ)

Here are some common questions beginners have about GCD in C++:

Q1: Which method should I use in real programs?
For modern C++, the std::gcd() function is recommended because it is concise, efficient, and reliable.

Q2: Can GCD be negative?
No, the GCD is always positive, even if one or both input numbers are negative.

Q3: Can GCD handle zero?
Yes, if one number is zero, the GCD is the other non-zero number. If both numbers are zero, the GCD is undefined.

Q4: Why learn loops or Euclidean methods?
Learning loops and the Euclidean algorithm helps beginners understand the logic behind GCD calculations and strengthens problem-solving skills.

Conclusion

Calculating the GCD of two numbers in C++ is a fundamental exercise that introduces important concepts like divisibility, loops, and algorithms. We explored four methods: the simple loop method, the Euclidean subtraction method, the optimized Euclidean modulo method, and the modern std::gcd() function. While loops and the Euclidean algorithm are excellent for learning, std::gcd() is the preferred approach for practical and professional programs. Practicing these methods helps beginners build a strong foundation in both mathematics and programming logic.

Additional & References

Understanding GCD is crucial for number theory problems, simplifying fractions, and computing LCM. Beginners should experiment with all methods and compare efficiency, then adopt std::gcd() for modern C++ coding.

Related Posts

Scroll to Top