一组超过2个整数的最大公约数

Question

Stack Overflow上有几个问题讨论如何找到两个值的最大公约数.一个好的答案显示了一个简洁的递归函数来做到这一点.

但是如何找到一组超过2个整数的GCD？我似乎无法找到这样的例子.

---

任何人都可以建议最有效的代码来实现这个功能吗？

static int GCD(int[] IntegerSet)
{
    // what goes here?
}

Answer 1

在这里你有代码示例使用LINQ和GCD方法来链接你的问题.它正在使用其他答案中描述的理论算法......GCD(a, b, c) = GCD(GCD(a, b), c)

static int GCD(int[] numbers)
{
    return numbers.Aggregate(GCD);
}

static int GCD(int a, int b)
{
    return b == 0 ? a : GCD(b, a % b);
}

Answer 2

您可以使用GCD的这个公共属性:

GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b)

假设您GCD(a, b)已经定义了很容易概括:

public class Program
{
    static void Main()
    {
        Console.WriteLine(GCD(new[] { 10, 15, 30, 45 }));
    }

    static int GCD(int a, int b)
    {
        return b == 0 ? a : GCD(b, a % b);
    }

    static int GCD(int[] integerSet)
    {
        return integerSet.Aggregate(GCD);
    }    
}