C# – Greatest Common Divisor from a set of more than 2 integers

algorithmcmath

There are several questions on Stack Overflow discussing how to find the Greatest Common Divisor of two values. One good answer shows a neat recursive function to do this.

But how can I find the GCD of a set of more than 2 integers? I can't seem to find an example of this.

Can anyone suggest the most efficient code to implement this function?

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

Best Answer

And here you have code example using LINQ and GCD method from question you linked. It is using theoretical algorithm described in other answers ... 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);
}
Related Topic