Popular recipes tagged "gcd"http://code.activestate.com/recipes/tags/gcd/popular/2016-03-03T07:12:28-08:00ActiveState Code RecipesExtended Euclidean Algorithm (Python) 2016-03-03T07:12:28-08:00Samuel James Ericksonhttp://code.activestate.com/recipes/users/4187478/http://code.activestate.com/recipes/578631-extended-euclidean-algorithm/ <p style="color: grey"> Python recipe 578631 by <a href="/recipes/users/4187478/">Samuel James Erickson</a> (<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/discrete/">discrete</a>, <a href="/recipes/tags/divisor/">divisor</a>, <a href="/recipes/tags/euclid/">euclid</a>, <a href="/recipes/tags/extended/">extended</a>, <a href="/recipes/tags/gcd/">gcd</a>, <a href="/recipes/tags/greatest/">greatest</a>, <a href="/recipes/tags/logarithm/">logarithm</a>). Revision 2. </p> <p>given input of integers a and b, this program returns GCD(a,b) along with integers x and y such that ax+by=GCD(a,b).</p> Greatest Common Divisor using Recursion in Python (Python) 2013-01-16T16:44:46-08:00Captain DeadBoneshttp://code.activestate.com/recipes/users/4184772/http://code.activestate.com/recipes/578421-greatest-common-divisor-using-recursion-in-python/ <p style="color: grey"> Python recipe 578421 by <a href="/recipes/users/4184772/">Captain DeadBones</a> (<a href="/recipes/tags/gcd/">gcd</a>, <a href="/recipes/tags/math/">math</a>, <a href="/recipes/tags/python/">python</a>). </p> <p>I wrote this little piece of code as part of my ongoing python-math projects. For more information please checkout <a href="http://thelivingpearl.com">The Living Pearl</a>. </p> GCD of an arbitrary list (Python) 2010-12-22T00:05:45-08:00Jason Schornhttp://code.activestate.com/recipes/users/4176312/http://code.activestate.com/recipes/577512-gcd-of-an-arbitrary-list/ <p style="color: grey"> Python recipe 577512 by <a href="/recipes/users/4176312/">Jason Schorn</a> (<a href="/recipes/tags/arbitrary/">arbitrary</a>, <a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/divisor/">divisor</a>, <a href="/recipes/tags/gcd/">gcd</a>, <a href="/recipes/tags/greatest/">greatest</a>, <a href="/recipes/tags/list/">list</a>, <a href="/recipes/tags/schorn/">schorn</a>). </p> <p>Given an arbitrary list (of length &gt;= 1) of positive integers, return the greatest common divisor (<code>gcd</code>) of the list.</p> Finding the GCD of a list of numbers (a.k.a. Reducing numbers in a list) (Python) 2010-07-06T18:52:55-07:00Stephen Akikihttp://code.activestate.com/recipes/users/4172143/http://code.activestate.com/recipes/577282-finding-the-gcd-of-a-list-of-numbers-aka-reducing-/ <p style="color: grey"> Python recipe 577282 by <a href="/recipes/users/4172143/">Stephen Akiki</a> (<a href="/recipes/tags/common/">common</a>, <a href="/recipes/tags/denominator/">denominator</a>, <a href="/recipes/tags/gcd/">gcd</a>, <a href="/recipes/tags/greatest/">greatest</a>, <a href="/recipes/tags/lisst/">lisst</a>, <a href="/recipes/tags/reduce/">reduce</a>). </p> <p><a href="http://akiscode.com/articles/gcd_of_a_list.shtml" rel="nofollow">http://akiscode.com/articles/gcd_of_a_list.shtml</a></p> <p>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.</p> <p>Why this works...</p> <p>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.</p>