c ++中的GCD函数没有cmath库

Question

我正在写一个混合数字类,需要一个快速简单的"最大公约数"函数.任何人都可以给我代码或代码的链接？

Answer 1

libstdc ++算法库有一个隐藏的gcd函数(我使用的是g ++ 4.6.3).

#include <iostream>
#include <algorithm>

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

别客气 :)

更新:正如@ chema989所指出的那样,在C++ 17中有标题std::gcd()可用的功能<numeric>.

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(如果您关心gcd,那么您可能会对std::lcm添加的内容感兴趣).

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)你(试图)消耗十亿左右的堆叠帧一样.递归的理想用例类似于二进制搜索,您可以在每次迭代时将解决方案空间减少一半.最大的公约除数也是解决方案空间迅速减少的因素,因此对大量堆栈使用的担忧在那里是没有根据的.

Answer 4

对于C++ 17,您可以使用std::gcd标头中定义的<numeric>:

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

Answer 5

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

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