Какой самый быстрый способ найти gcd из n чисел?

Question

Какой самый быстрый способ вычислить наибольший общий делитель n чисел?

Answer 1

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 2

//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 3

Вот метод gcd, который использует свойство gcd (a, b, c) = gcd (a, gcd (b, c)).
Он использует метод gcd BigInteger, так как он уже оптимизирован.

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 4

Вот ответ, который я искал. Самый лучший способ найти gcd из n чисел - это использовать recursion.ie gcd (a, b, c) = gcd (gcd (a, b), c). Но я получал тайм-ауты в некоторых программах, когда я делал это.

Оптимизация, которая была здесь необходима, заключалась в том, что рекурсия должна решаться с использованием алгоритма быстрого умножения матриц.