超过两个数字的欧几里德最大公约数

Question

有人可以举一个例子来找到超过两个数字的最大公约数算法吗？

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

Answer 1

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

哦，这可以很容易并行，因为操作是交换/关联。

Answer 2

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

Answer 3

在Java中（不是最佳）：

public static int GCD(int[] a){ 
    int j = 0; 

    boolean b=true; 
    for (int i = 1; i < a.length; i++) { 
     if(a[i]!=a[i-1]){ 
      b=false; 
      break; 
     } 
    } 
    if(b)return a[0]; 
    j=LeastNonZero(a); 
    System.out.println(j); 
    for (int i = 0; i < a.length; i++) { 
     if(a[i]!=j)a[i]=a[i]-j; 
    } 
    System.out.println(Arrays.toString(a)); 
    return GCD(a); 
} 

public static int LeastNonZero(int[] a){ 
    int b = 0; 
    for (int i : a) { 
     if(i!=0){ 
      if(b==0||i<b)b=i; 
     } 
    } 
    return b; 
} 

Answer 4

我刚刚更新了一个wiki网页上这一点。

[https://en.wikipedia.org/wiki/Binary_GCD_algorithm#C.2B.2B_template_class]

这需要术语的任意数量。 使用GCD（5，2，30，25，90，12）;

template<typename AType> AType GCD(int nargs, ...) 
{ 
    va_list arglist; 
    va_start(arglist, nargs); 

    AType *terms = new AType[nargs]; 

    // put values into an array 
    for (int i = 0; i < nargs; i++) 
    { 
     terms[i] = va_arg(arglist, AType); 
     if (terms[i] < 0) 
     { 
      va_end(arglist); 
      return (AType)0; 
     } 
    } 
    va_end(arglist); 

    int shift = 0; 
    int numEven = 0; 
    int numOdd = 0; 
    int smallindex = -1; 

    do 
    { 
     numEven = 0; 
     numOdd = 0; 
     smallindex = -1; 

     // count number of even and odd 
     for (int i = 0; i < nargs; i++) 
     { 
      if (terms[i] == 0) 
       continue; 

      if (terms[i] & 1) 
       numOdd++; 
      else 
       numEven++; 

      if ((smallindex < 0) || terms[i] < terms[smallindex]) 
      { 
       smallindex = i; 
      } 
     } 

     // check for exit 
     if (numEven + numOdd == 1) 
      continue; 

     // If everything in S is even, divide everything in S by 2, and then multiply the final answer by 2 at the end. 
     if (numOdd == 0) 
     { 
      shift++; 
      for (int i = 0; i < nargs; i++) 
      { 
       if (terms[i] == 0) 
        continue; 

       terms[i] >>= 1; 
      } 
     } 

     // If some numbers in S are even and some are odd, divide all the even numbers by 2. 
     if (numEven > 0 && numOdd > 0) 
     { 
      for (int i = 0; i < nargs; i++) 
      { 
       if (terms[i] == 0) 
        continue; 

       if ((terms[i] & 1) == 0) 
        terms[i] >>= 1; 
      } 
     } 

     //If every number in S is odd, then choose an arbitrary element of S and call it k. 
     //Replace every other element, say n, with | n−k |/2. 
     if (numEven == 0) 
     { 
      for (int i = 0; i < nargs; i++) 
      { 
       if (i == smallindex || terms[i] == 0) 
        continue; 

       terms[i] = abs(terms[i] - terms[smallindex]) >> 1; 
      } 
     } 

    } while (numEven + numOdd > 1); 

    // only one remaining element multiply the final answer by 2s at the end. 
    for (int i = 0; i < nargs; i++) 
    { 
     if (terms[i] == 0) 
      continue; 

     return terms[i] << shift; 
    } 
    return 0; 
}; 

Answer 5

有点晚了，我知道的一方，但一个简单的JavaScript实现，利用算法的萨姆·哈威尔的描述：

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 

Answer 6

对于golang，使用剩余

func GetGCD(a, b int) int { 
    for b != 0 { 
     a, b = b, a%b 
    } 
    return a 
} 
func GetGCDFromList(numbers []int) int { 
    var gdc = numbers[0] 
    for i := 1; i < len(numbers); i++ { 
     number := numbers[i] 
     gdc = GetGCD(gdc, number) 
    } 
    return gdc 
}