获取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( n1, n2, .... nx )可以通过递增计算两个数字的GCD来计算多个数字的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;    
}

Answer 2

试试这个,

public static void main(String[] args) {
    System.out.println(" GDC: " + getGdc(12, 48, 24, 5));
    System.out.println(" GDC: " + getGdc(12, 48, 24));
}

public static int getGdc(int... x) {
    // get the smallest of all number no need to check for higher values
    int smallest = getSmallest(x);

    for(int i = smallest; i >= 1; i--) {
       int j;
       for(j = 0; j < x.length; ++j) {
           if(x[j] % i != 0)
               break;
       }
       // if we pass through the array with all % == 0 return the value
       if(j == x.length)
           return i;
    }
    // so the only possible is 1
    return 1;
}

// return smallest number of an array of int
public static int getSmallest(int[] x) {
    int smallest = x[0];
    for(int i = 1; i < x.length; ++i) {
        if(x[i] < smallest)
            smallest = x[i];
    }
    return smallest;
}

请参阅本也更多.希望这可以帮助