C++ sans cmath 库中的 GCD 函数

GCD function in c++ sans cmath library

提问by Connor Black

I'm writing a mixed numeral class and need a quick and easy 'greatest common divisor' function. Can anyone give me the code or a link to the code?

我正在编写一个混合数字类，需要一个快速简单的“最大公约数”函数。谁能给我代码或代码的链接？

回答by Tomasz Pos?uszny

The libstdc++ algorithm library has a hidden gcd function (I'm using g++ 4.6.3).

libstdc++ 算法库有一个隐藏的 gcd 函数（我使用的是 g++ 4.6.3）。

#include <iostream>
#include <algorithm>

int main()
{
  cout << std::__gcd(100,24);
  return 0;
}

You are welcome :)

不客气 ：）

UPDATE: As @chema989 noted it, in C++17 there is std::gcd()function available with <numeric>header.

更新：正如@chema989 所指出的，在 C++17 中有std::gcd()可用的函数和<numeric>头文件。

回答by Jerry Coffin

I'm tempted to vote to close -- it seems difficult to believe that an implementation would be hard to find, but who knows for sure.

我很想投票结束——似乎很难相信很难找到实现，但谁知道呢。

template <typename Number>
Number GCD(Number u, Number v) {
    while (v != 0) {
        Number r = u % v;
        u = v;
        v = r;
    }
    return u;
}

In C++ 17 or newer, you can just #include <numeric>, and use std::gcd(and if you care, about the gcd, chances are pretty fair that you'll be interested in the std::lcmthat was added as well).

在 C++ 17 或更高版本中，您可以只#include <numeric>使用 , 和使用std::gcd（如果您关心 gcd，您很可能也会对std::lcm添加的感兴趣）。

回答by paxdiablo

A quick recursive version:

快速递归版本：

unsigned int gcd (unsigned int n1, unsigned int n2) {
    return (n2 == 0) ? n1 : gcd (n2, n1 % n2);
}

or the equivalent iterative version if you're violently opposed to recursion ^(a):

或等效的迭代版本，如果您强烈反对递归^(a)：

unsigned int gcd (unsigned int n1, unsigned int n2) {
    unsigned int tmp;
    while (n2 != 0) {
        tmp = n1;
        n1 = n2;
        n2 = tmp % n2;
    }
    return n1;
}

Just substitute in your own data type, zero comparison, assignment and modulus method (if you're using some non-basic type like a bignumclass, for example).

只需替换您自己的数据类型、零比较、赋值和模数方法（例如，如果您使用一些非基本类型，如bignum类）。

This function actually came from an earlier answer of minefor working out integral aspect ratios for screen sizes but the original source was the Euclidean algorithm I learnt a long time ago, detailed here on Wikipediaif you want to know the math behind it.

这个函数实际上来自我早期的答案，用于计算屏幕尺寸的整数纵横比，但原始来源是我很久以前学到的欧几里得算法，如果你想知道它背后的数学，请在维基百科上详细说明。

---

---

^(a)The problem with some recursive solutions is that they approach the answer so slowly you tend to run out of stack space before you get there, such as with the very badly thought out (pseudo-code):

^(a)一些递归解决方案的问题是它们接近答案的速度太慢，以至于在到达那里之前往往会耗尽堆栈空间，例如经过深思熟虑的（伪代码）：

def sum (a:unsigned, b:unsigned):
    if b == 0: return a
    return sum (a + 1, b - 1)

You'll find that very expensive on something like sum (1, 1000000000)as you (try to) use up a billion or so stack frames. The ideal use case for recursion is something like a binary search where you reduce the solution space by half for each iteration. The greatest common divisor is also one where the solution space reduces rapidly so fears about massive stack use are unfounded there.

sum (1, 1000000000)当您（尝试）使用大约十亿个堆栈帧时，您会发现它非常昂贵。递归的理想用例类似于二分搜索，每次迭代将解决方案空间减少一半。最大公约数也是解决方案空间迅速减少的一个，因此对大量堆栈使用的担忧是没有根据的。

回答by chema989

For C++17 you can use std::gcddefined in header <numeric>:

对于 C++17，您可以使用std::gcd在 header 中定义<numeric>：

auto res = std::gcd(10, 20);

回答by David Nehme

The Euclideanalgorithm is quite easy to write in C.

该欧几里德算法是很容易在C.写

int gcd(int a, int b) {
  while (b != 0)  {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}