# C++17 - find the greatest common divisor, gcd, of two or more integers

## Posted on October 25, 2019 by Paul

In this article, I will show you how to find the gcd - greatest common divisor of two or more integers with C++, by using two implementations of the classical Euclid algorithm. As a side note, the C++ standard library has a std::gcd function that can calculate the gcd of two numbers and I will also show you how to use the STL version. Implementing an algorithm from scratch is the best way to understand it, even though in practice one should use as much as possible the solution already provided by the language standard library.

There is also a video version of this tutorial:

By definition, the *gcd* of two or more integers, that are not all zero, is the largest positive integer that divides all these numbers. For example:

It is also useful to define:

Here are couple of properties of the *gcd* function:

The Euclid algorithm, or method, uses the fact that for two positive integers a and b:

Here is a worked example of using Euclid’s method to calculate gcd(15, 9):

finally, we can write:

Please note that, in the above calculations, we’ve used properties (1) and (4) of the *gcd* function.

At this point, we can write a C++ driver function that will ensure that we are doing the actual calculations only for positive integers:

Next, we’ll implement the iterative version of Euclid’s algorithm:

In the above function, we keep subtracting b from a and swapping a with b if a is less than b, until a becomes zero, at which point b contains the answer.

Line 4 in the above function calls a *swap* function. In principle we can use std::swap from the standard library, however I chose to implement my own version, since we are doing a *from scratch* version of *gcd*. Here is the implementation of my *swap* function:

Let’s test the above functions:

If you build the above program with a standard C++17 compiler you should get no error and all five tests should pass at compile time.

If you want to trigger error messages at compile time, you can modify the *main* function from the above code, e.g.:

This is what I see, if I build the above program with *GCC 9.2* on a macOS machine:

Next, let’s implement a recursive version of the Euclid algorithm. The driver function is basically the same, except that it will call *euclid_gcd_recursive* on line 13:

Next, we’ll implement the recursive version of Euclid’s algorithm:

Finally, let’s modify the *main* function by adding compile time tests for the recursive algorithm:

An optimization of the Euclid algorithm for calculating *gcd* is to replace the repetitive subtraction of *b* from *a* with the modulo operator. For example, this is the recursive version of the algorithm with the above optimization:

I’ve moved the optimized version of the above functions to file named *gcd.h*.

It is interesting to implement a *gcd* function that finds the greatest common divisor of a collection of integers, e.g.:

As promised, here is an example of using the standard library *gcd* implementation:

What about using *std::gcd* with a collection of integers? While you can use the above example with a loop over a vector, a simpler approach is to use std::reduce:

Please note that the above example will not compile with *GCC 9*! It works with *VS 2019*, *Clang 9* and *GCC 10*.

You can find the complete source code on the GitHub repository for this article.

If you want to learn more about C++17 I would recommend reading C++17 in Detail by Bartlomiej Filipek:

or, C++17 - The Complete Guide by Nicolai M. Josuttis: