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

Question

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

Answer 1

没有递归:

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 2

您可能希望先对数字进行排序,然后从最小的两个数字开始递归计算gcd.

Answer 3

您应该使用Lehmer 的 GCD 算法。