找到n个数字的gcd最快的方法是什么？

Question

计算n个数的最大公约数的最快方法是什么？

Answer 1

您应该使用Lehmer's GCD algorithm。

Answer 2

没有递归：

int result = numbers[0]; 
for(int i = 1; i < numbers.length; i++){ 
    result = gcd(result, numbers[i]); 
} 
return result; 

对于非常大的阵列，它可能会更快使用的fork-join模式，在那里你分割你的阵列和并行计算GCDS。这里是一些伪代码：

int calculateGCD(int[] numbers){ 
    if(numbers.length <= 2){ 
     return gcd(numbers);  
    } 
    else { 
     INVOKE-IN-PARALLEL { 
      left = calculateGCD(extractLeftHalf(numbers)); 
      right = calculateGCD(extractRightHalf(numbers)); 
     } 
     return gcd(left,right); 
    } 
} 

Answer 3

你可能想先排序数字，并从最小的两个数字开始递归计算gcd。

Answer 4

如果您有很多的小数字，分解可能实际上更快。

//Java 
int[] array = {60, 90, 45}; 
int gcd = 1; 
outer: for (int d = 2; true; d += 1 + (d % 2)) { 
    boolean any = false; 
    do { 
     boolean all = true; 
     any = false; 
     boolean ready = true; 
     for (int i = 0; i < array.length; i++) { 
      ready &= (array[i] == 1); 
      if (array[i] % d == 0) { 
       any = true; 
       array[i] /= d; 
      } else all = false; 
     } 
     if (all) gcd *= d; 
     if (ready) break outer; 
    } while (any); 
} 
System.out.println(gcd); 

（适用于一些例子，但不是真正的考验）

Answer 5

这里是我一直在寻找的答案。 找到n个数字gcd的最好方法是使用recursion.ie gcd（a，b，c）= gcd（gcd（a，b），c）。但是当我这样做时，我在某些程序中超时。

这里需要的优化是递归应该使用快速矩阵乘法算法来解决。

Answer 6

这是一个使用gcd（a，b，c）= gcd（a，gcd（b，c））属性的gcd方法。
它使用BigInteger的gcd方法，因为它已经被优化。

public static BigInteger gcd(BigInteger[] parts){ 
    BigInteger gcd = parts[0]; 
    for(int i = 1; i < parts.length; i++) 
     gcd = parts[i].gcd(gcd); 
    return gcd; 
} 

Answer 7

C++ 17

我写了这个功能，用于通过使用C++的内置__gcd（INT A，INT B）函数计算n个数字的最大公约数。

int gcd(vector<int> vec, int vsize) 
{ 
    int gcd = vec[0]; 
    for (int i = 1; i < vsize; i++) 
    { 
     gcd = __gcd(gcd, vec[i]); 
    } 
    return gcd; 
} 

要了解更多关于此功能的信息，请访问this link。

另请参阅以下链接中的Dijkstra's GCD algorithm。它的工作没有分裂。所以它可能是稍快（请纠正我，如果我错了。）

Answer 8

//Recursive solution to get the GCD of Two Numbers 

long long int gcd(long long int a,long long int b)<br> 
{ 
    return b==0 ? a : gcd(b,a%b); 
} 
int main(){ 
    long long int a,b; 
    cin>>a>>b; 
    if(a>b) cout<<gcd(a,b); 
    else cout<<gcd(b,a); 
return 0; 
} 

Answer 9

使用欧几里德算法：

function gcd(a, b) 
while b ≠ 0 
    t := b; 
    b := a mod b; 
    a := t; 
return a; 

你运用它的前两个数字，然后将结果与第三个数字，等...：

read(a); 
read(b); 

result := gcd(a, b); 
i := 3; 
while(i <= n){ 
    read(a) 
    result := gcd(result, a); 
} 
print(result); 

Answer 10

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

class GCDArray{ 
    public static int [] extractLeftHalf(int [] numbers) 
    { 
     int l =numbers.length/2; 
     int arr[] = Arrays.copyOf(numbers, l+1); 
     return arr; 
    } 

    public static int [] extractRightHalf(int [] numbers) 
    { 
     int l =numbers.length/2; 
     int arr[] = Arrays.copyOfRange(numbers,l+1, numbers.length); 
     return arr; 
    } 

    public static int gcd(int[] numbers) 
    { 
     if(numbers.length==1) 
      return numbers[0]; 
     else { 
      int x = numbers[0]; 
      int y = numbers[1]; 
      while(y%x!=0) 
      { 
       int rem = y%x; 
       y = x; 
       x = rem; 
      } 
      return x; 
     } 
    } 
    public static int gcd(int x,int y) 
    { 
      while(y%x!=0) 
      { 
       int rem = y%x; 
       y = x; 
       x = rem; 
      } 
      return x; 

    } 
    public static int calculateGCD(int[] numbers){ 
     if(numbers.length <= 2){ 
      return gcd(numbers);  
     } 
     else { 

        int left = calculateGCD(extractLeftHalf(numbers)); 
        int right = calculateGCD(extractRightHalf(numbers)); 

      return gcd(left,right); 
     } 
    } 
    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     int n = sc.nextInt(); 
     int arr[] = new int[n]; 
     for(int i=0;i<n;i++){ 
      arr[i]=sc.nextInt(); 
     } 
     System.out.println(calculateGCD(arr)); 
    } 
} 

**

以上是java工作代码.....的伪代码，其中是 已经通过https://stackoverflow.com/users/7412/dogbane

**

Answer 11

这里下面提的是C程序的源代码，以找到使用阵列N个数的HCF。

#include<stdio.h> 
 

 
int main() 
 
{ 
 
    int n,i,gcd; 
 
    printf("Enter how many no.s u want to find gcd : "); 
 
    scanf("%d",&n); 
 
    int arr[n]; 
 
    printf("\nEnter your numbers below :- \n "); 
 
    for(i=0;i<n;i++) 
 
    { 
 
     printf("\nEnter your %d number = ",i+1); 
 
     scanf("%d",&arr[i]); 
 
    } 
 
    gcd=arr[0]; 
 
    int j=1; 
 
    while(j<n) 
 
    { 
 
     if(arr[j]%gcd==0) 
 
     { 
 
      j++; 
 
     } 
 
     else 
 
     { 
 
      gcd=arr[j]%gcd; 
 
      i++; 
 
     } 
 
    } 
 
    printf("\nGCD of k no.s = %d ",gcd); 
 
    return 0; 
 
}

欲了解更多请参考本website进一步澄清.......

Answer 12

您可以使用分而治之。要计算gcdN（[]），请将列表分为前半部分和后半部分。如果每个列表只有一个数字。你使用gcd2（n1，n2）来计算。

我刚写了一个快速示例代码。 （假设列表中的所有数字均为正数）

def gcdN(nums): 
    n = len(nums) 
    if n == 0: return "ERROR" 
    if n == 1: return nums[0] 
    if n >= 2: return gcd2(gcdN(nums[:n//2]), gcdN(nums[n//2:])) 

def gcd2(n1, n2): 
    for num in xrange(min(n1, n2), 0, -1): 
     if n1 % num == 0 and n2 % num == 0: 
      return num 

Answer 13

递归JavaScript（ES6）对任何位数的单行数。

const gcd = (a, b, ...c) => b ? gcd(b, a % b, ...c) : c.length ? gcd(a, ...c) : Math.abs(a);