Greatest Common Divisor from a set of more than 2 integers

user_180215 0
Viewed 30313

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?
}
math algorithm c#
13 Answers
let a = 3
let b = 9

func gcd(a:Int, b:Int) -> Int {
    if a == b {
        return a
    }
    else {
        if a > b {
            return gcd(a:a-b,b:b)
        }
        else {
            return gcd(a:a,b:b-a)
        }
    }
}
print(gcd(a:a, b:b))
user_101118250

GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), 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);
  }
}
user_84728350

By using this, you can pass multiple values as well in the form of array:-

// pass all the values in array and call findGCD function
    int findGCD(int arr[], int n) 
    { 
        int gcd = arr[0]; 
        for (int i = 1; i < n; i++) {
            gcd = getGcd(arr[i], gcd); 
        }

        return gcd; 
    } 

// check for gcd
    int getGcd(int x, int y) 
    { 
        if (x == 0) 
            return y; 
        return gcd(y % x, x); 
    }
user_89587290
Related