Welcome, guest | Sign In | My Account | Store | Cart

http://akiscode.com/articles/gcd_of_a_list.shtml

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) ```

#### 1 comment

Jason Schorn 13 years, 4 months ago

Just a couple of points to make:

1. 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).

2. Without coding for errors/awful user input try.

``````def GCD(a,b):
return abs(a) if b==0 else GCD(b, a%b)

def GCD_List(*args):
return reduce(GCD, args)
``````

Note the following:

1. 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".

2. 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:

``````gcd( some_list_where_length_>=_1 )
...do some stuff
...return the gcd
``````
 Created by Stephen Akiki on Tue, 6 Jul 2010 (MIT)