The std::gcd Function in C++

Use the
std::gcd
Function to Calculate Greatest Common Divisor of Two Integers in C++ 
Use the
std::lcm
Function to Calculate Least Common Multiple of Two Integers in C++ 
Use the
std::midpoint
Function to Calculate Middle Point of Two Numbers in C++
This article will explain how to utilize std::gcd
and other useful mathematical functions from STL numerics library in C++.
Use the std::gcd
Function to Calculate Greatest Common Divisor of Two Integers in C++
STL provides multiple algorithms using <algorithm>
header, but it also provides powerful mathematical functions, some of which can be considered numeric algorithms. These functions are provided using the header  numeric
.
We will explore the std::gcd
function that computes the greatest common divisor of two integers. A greatest common divisor is the largest positive integer that divides each of the given integers.
std::gcd
takes two integer values (m
and n
) and returns the greatest common divisor of m
and n
. If both m
and n
happen to have zero, the function also returns zero. The following example code demonstrates the basic usage of std::gcd
and prints the corresponding results to the console.
#include <iostream>
#include <vector>
#include <iomanip>
#include <numeric>
using std::cout;
using std::endl;
using std::vector;
using std::setw;
int main() {
std::vector<std::pair<int, int>> vec = { {12125, 1235},
{124, 1122},
{1235, 321},
{12, 144} };
for (const auto &item : vec) {
cout << "Greatest common divisor of " << setw(5) << item.first <<
" and " << setw(5) << item.second << " is " <<
std::gcd(item.first, item.second) << endl;
}
return EXIT_SUCCESS;
}
Output:
Greatest common divisor of 12125 and 1235 is 5
Greatest common divisor of 124 and 1122 is 2
Greatest common divisor of 1235 and 321 is 1
Greatest common divisor of 12 and 144 is 1
Use the std::lcm
Function to Calculate Least Common Multiple of Two Integers in C++
Another similar function provided in the numerics library is std::lcm
, which calculates the least common multiple of two integers. The function accepts two integers similar to the std:gcd
and returns the least common multiple of m
and n
(denoting the arguments).
Notice that both of these functions have constexpr
specifier, which implies it is possible that they are used in constant expressions, and also the function gets inline
classification.
#include <iostream>
#include <vector>
#include <iomanip>
#include <numeric>
using std::cout;
using std::endl;
using std::vector;
using std::setw;
int main() {
std::vector<std::pair<int, int>> vec = { {12125, 1235},
{124, 1122},
{1235, 321},
{12, 144} };
for (const auto &item : vec) {
cout << "Least common multiple of " << setw(5) << item.first <<
" and " << setw(5) << item.second << " is " <<
std::lcm(item.first, item.second) << endl;
}
return EXIT_SUCCESS;
}
Output:
Least common multiple of 12125 and 1235 is 2994875
Least common multiple of 124 and 1122 is 69564
Least common multiple of 1235 and 321 is 396435
Least common multiple of 12 and 144 is 144
Use the std::midpoint
Function to Calculate Middle Point of Two Numbers in C++
std::midpoint
is a capable function for calculating the half of two given numbers without the user worrying about the overflows. Namely, if we try to calculate the half of two large integers, the sum of which is bigger than the upper bound of the 64bit integer, then we get the overflow, and the result will be incorrect.
As an example, the following code snippet tries to find the midpoint of two integers, where one is the same as the maximum number that can be stored in uint64_t,
and the other one is less by ten. Notice that the calculation using the usual arithmetic operators yields the wrong number while std::midpoint
returns the correct result.
Mind though that this function has been part of the language since the C++20 standard and may not be available on older versions. std::midpoint
works on pointer values as well, but the given pointers should be elements of the same array. Otherwise, the behavior is undefined.
#include <iostream>
#include <vector>
#include <iomanip>
#include <numeric>
using std::cout;
using std::endl;
using std::vector;
using std::setw;
int main() {
uint64_t a = std::numeric_limits<uint64_t>::max();
uint64_t b = std::numeric_limits<uint64_t>::max()  10;
cout << "a: " << a << '\n'
<< "b: " << b << '\n'
<< "Incorrect: " << setw(20)
<< (a + b) / 2 << '\n'
<< "Correct : " << setw(20)
<< std::midpoint(a, b) << endl;
return EXIT_SUCCESS;
}
Output:
a: 18446744073709551615
b: 18446744073709551605
Incorrect: 9223372036854775802
Correct : 18446744073709551610