1

I currently use this code to find gcd and lcm

def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

def lcm(a, b):
    result = a*b/gcd(a,b)
    return result

But what if I want to do this for a list of numbers e.g. [4,5,7,1,5,7,10,1,16,24] etc? Am I constrained to loops?

John Smith
  • 11,678
  • 17
  • 46
  • 51
  • You could save the computed values in a hashmap of some kind and first check there if you've already computed the value, if you have you don't need to recalculate it, otherwise you would have to. – lfxgroove Jan 10 '12 at 16:18
  • @Anton. In addition, save (cache) all intermediate results in memory too and check the cache each iteration. For sufficiently large lists of sufficiently large numbers, this will be faster. – Martijn Jan 10 '12 at 16:29
  • I know how to use memoization classifiers; how could I use those here? – John Smith Jan 10 '12 at 16:31
  • possible duplicate of [How to find GCF, LCM on a set of numbers](http://stackoverflow.com/questions/4201860/how-to-find-gcf-lcm-on-a-set-of-numbers) – Chris J Jan 10 '12 at 16:37
  • @ChrisJ Since that question is specifically about Java and this one is not, it would seem that it fails to be an **exact** duplicate. – Michael McGowan Jan 10 '12 at 16:41
  • 2
    The answers to that question though pretty much provide the answer, if not in language, then they refer to the appropriate algorithm. – Chris J Jan 10 '12 at 22:09
  • @ChrisJ Well also note that the accepted answer to that question is basically already provided in the body of *this* question...this question is quite explicitly asking how to do it for more than 2 numbers. – Michael McGowan Jan 16 '12 at 21:16

3 Answers3

1
from fractions import gcd
def lcm(a, b):
    return (a * b) // gcd(a, b)
Pankaj Kumar
  • 179
  • 1
  • 9
0

You could use a recursive technique:

def gcd(a, b):
   if b == 0:
      return a
   else:
      return gcd(b, a%b)

Store all your GCD values in a hash map. So, when it does the recursive step, it first accesses the hash map to see if the GCD of the smaller numbers has already been computed, which will save a lot of time if you were doing this for a large range of inputs.

HexTree
  • 148
  • 1
  • 7
0

As mentioned by Chris J this SO question provides the algorithm. Here is a python version of the answer that uses the reduce built-in and the fractions module that has been around since version 2.6.

import fractions

def gcd(*values):
    return reduce(fractions.gcd, values)
Community
  • 1
  • 1
President James K. Polk
  • 40,516
  • 21
  • 95
  • 125