找到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);