欧几里德对两个以上数字的最大公约数

Question

有人可以举例说明两个以上数字的最大公约数算法吗？

我相信编程语言并不重要.

Answer 1

从第一对开始并获得他们的GCD,然后获取该结果的GCD和下一个数字.显而易见的优化是,如果正在运行的GCD达到1,你可以停止.我正在看这个,看看是否还有其他优化.:)

哦,这可以很容易地并行化,因为操作是可交换/关联的.

Answer 2

3个数字的GCD可以计算为gcd(a, b, c) = gcd(gcd(a, b), c).您可以迭代地应用欧几里德算法,扩展欧几里德算法或二进制GCD算法并得到答案.不幸的是,我不知道有任何其他(更聪明的？)方法来寻找GCD.

Answer 3

我知道参加聚会有点晚了，但是一个简单的 JavaScript 实现，利用了 Sam Harwell 对算法的描述：

function euclideanAlgorithm(a, b) {
    if(b === 0) {
        return a;
    }
    const remainder = a % b;
    return euclideanAlgorithm(b, remainder)
}

function gcdMultipleNumbers(...args) { //ES6 used here, change as appropriate
  const gcd = args.reduce((memo, next) => {
      return euclideanAlgorithm(memo, next)}
  );

  return gcd;
}

gcdMultipleNumbers(48,16,24,96) //8