This python code snippet allows you to find the GCD of a list of numbers, after this it is a simple matter of diving all the numbers in the list by the GCD to reduce it.
Why this works...
The GCD of a list of numbers [a, b, c] is GCD(GCD(a, b), c). The reduce function does exactly this and thus gives you the GCD of all the numbers in the list.
Python, 23 lines
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
# http://akiscode.com/articles/gcd_of_a_list.shtml # Copyright (c) 2010 Stephen Akiki # MIT License (Means you can do whatever you want with this) # See http://www.opensource.org/licenses/mit-license.php # Error Codes: # None def GCD(a,b): """ The Euclidean Algorithm """ a = abs(a) b = abs(b) while a: a, b = b%a, a return b def GCD_List(list): """ Finds the GCD of numbers in a list. Input: List of numbers you want to find the GCD of E.g. [8, 24, 12] Returns: GCD of all numbers """ return reduce(GCD, list)
Just a couple of points to make:
Why abs()? Either assume the person using the function knows to use positive integers or note that gcd(-6, 8) = (+-)2 are valid answers despite not adhering to the Euclidean algorithm. Alternatively, try return abs(b).
Without coding for errors/awful user input try.
Note the following:
The use of *args let you use the function as GCD_List(a,b,c, ...) thereby saving yourself and your users the hassle of a whopping two extra key-strokes. I know it's rather ri-donk-ulous but programmers tend to appreciate the motto "less is more".
You can use 'a%b' or 'b%a' just make sure you adjust the above code accordingly.
As a final exercise see if you can create a single function such as: