Given an arbitrary list (of length >= 1) of positive integers, return the greatest common divisor (
gcd) of the list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
#!/usr/bin/python def gcd(*args): if len(args) == 1: return args L = list(args) while len(L) > 1: a = L[len(L) - 2] b = L[len(L) - 1] L = L[:len(L) - 2] while a: a, b = b%a, a L.append(b) return abs(b) #if __name__ == "__main__": print gcd(68, 14, 9, 36, 126)
We utilize the fact the
gcd is associative, i.e.
gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)), in order to compute the
gcd of an arbitrary list of positive integers. You should note that we do NOT check user input for such things as:
gcd(-3, 9) or
gcd(3.14159, 2.71828). Further, the desired end result could be completed as follows:
def g(a, b): return a if b==0 else g(b, a%b)
def gcd(*args): return reduce(g, args)
using less code but the ideas was to build a single function that computes the
gcd of some list of integers. Enjoy and let me know if you find a more succinct way.