java - 求n个数的gcd

Question

这似乎是一个简单的问题，但我找不到解决方案。我必须找到n个数的gcd。

public int getGCD(int a, int b) {
 if (b == 0) { return a; }
 else { return getGCD(b, a%b); }
}

这是计算两个数字的gcd的流行递归方法。但如果我需要得到 3, 4, 5... n 个数字的 gcd 呢？我想做这样的事情:

public int getGCD(int[] a) {
 //the code  
}

有一个整数数组作为参数，但我不知道代码。您有什么建议吗？

Answer 1

多个数字的 GCD gcd( n1, n2, .... nx ) 可以通过增量计算两个数字的 GCD 来计算:

gcd( n1, n2, .... nx ) == gcd( n1, gcd( n2, gcd( ... , nx ) ) )

所有数字的每个除数都必须是这些数字的任何子集的除数。这又导出了上面的公式。

通过对两个数字重复使用给定的 getGCD(int, int) 函数，我们可以创建一个额外的重载，该重载采用一个或多个数字的列表:

public int getGCD(int a, int b) {
 // implementation for two numbers goes here
}

public int getGCD(int[] a) {
  // the GCD of a number with itself is... itself
  int gcd = a[0];

  // compute incrementally
  for( int i=1; i<a.length; i++ ) {
    gcd = getGCD( gcd, a[i] );
  }

  // return result
  return gcd;    
}