C ++中不使用cmath库的GCD函数

Question

我正在编写一个混合数字类，并需要一个快速简单的“最大公约数”功能。有人能给我提供代码或代码链接吗？

我正在编写一个混合数字类，并需要一个快速简单的“最大公约数”功能。有人能给我提供代码或代码链接吗？

- Connor Black

---

这里有一堆有趣的：http://codegolf.stackexchange.com/questions/35587/ - technosaurus

Answer 1

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

#include <iostream>
#include <algorithm>

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

欢迎您 :)

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

- Tomasz Posłuszny

---

你不应该依赖于未记录的功能，因为它们有可能在库的更新版本中发生变化。 - vmrob

它是否适用于MSVC？ - Naseef Chowdhury

@vmrob：同意。你可以随时从STL中复制实现。Mbt925：完成。 - Tomasz Posłuszny

那听起来像是作弊 ;) - moldovean

Answer 2

我倾向于投票关闭此问题 - 看起来很难相信找不到一个实现，但谁知道呢。

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

在C++17或更新版本中，您只需包含#include <numeric>，然后使用std::gcd（如果您关心最大公约数，那么很可能您也会对新增的std::lcm感兴趣）。

- Jerry Coffin

---

谢谢。我刚刚在谷歌上搜索了好20分钟，但没有找到任何明确的结果。 - Connor Black

@JerryCoffin: 为什么不用模板来解决这个问题呢？ - einpoklum

Answer 3

一个快速的递归版本：

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

或者，如果您非常反对递归，可以使用其等价的迭代版本^(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;
}

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

这个函数实际上来自于我以前为屏幕尺寸计算整数宽高比的 回答中，但最初的来源是我很久以前学过的欧几里得算法，详细资料可在 维基百科 上查看。

---

^（a） 一些递归解决方案的问题在于它们接近答案的速度如此之慢，以至于你在到达目的地之前就会耗尽堆栈空间，例如下面这个极其糟糕的伪代码：

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

像 sum(1, 1000000000) 这样的计算会在使用超过数十亿个栈帧时非常昂贵。递归的理想用例是二分查找，每次迭代将解决方案空间减少一半。最大公约数也是这样，其解决方案空间迅速缩小，因此对于巨大的栈使用的担忧是没有必要的。

- paxdiablo

---

+1 你甚至可以添加 template<class Integral> 来替换 int，在函数前加上 constexpr 关键字，这样你就有了一个漂亮的编译时/运行时通用函数。 - authchir

你的第二个方法可能有错别字。应该是 return n1 吗？此时 n2 的定义总是为零。 - Jim Blackler

做得好，@Jim，已经修复了。 - paxdiablo

Answer 4

如果你使用C++17，你可以使用在头文件<numeric>中定义的std::gcd：

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

- chema989

Answer 5

欧几里得算法在C语言中编写起来非常简单。

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

- David Nehme