CODEWITHSUNDEEP
mathgreatest-common-divisorlcm
John Smith
John Smith

Reputation: 12236

How to get GCD and LCM of a range of numbers efficiently?

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?

Upvotes: 1

Views: 2296

Answers (3)

Pankaj Kumar
Pankaj Kumar

Reputation: 189

from fractions import gcd
def lcm(a, b):
    return (a * b) // gcd(a, b)

Upvotes: 1

President James K. Polk
President James K. Polk

Reputation: 41967

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)

Upvotes: 0

HexTree
HexTree

Reputation: 148

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.

Upvotes: 0

Related Questions