30

I have written a code to find out the LCM (Lowest Common Multiple) of a list of numbers but there appears to be an error in my code. The code is given below:

def final_lcm(thelist):
   previous_thelist = thelist
   prime_thelist = list(set(thelist) - set(returns_new_thelist(previous_thelist))
   factors = 1
   for i in prime_thelist:
       factors = factors*i
   new_thelist = returns_new_thelist(previous_thelist)
   for i in range(1, 10000000000):
       s_empty = []
       for j in new_thelist:
           if i % j  == 0:
               s_empty.append(True)
       if len(new_thelist) == len(s_empty):
           initial_lcm = i
           break
   final_lcm = factor*initial_lcm
   return final_lcm



def returns_new_thelist(ll):
    if 3 in ll:
        ll.remove(3)
    for i in ll:
        if checks_if_prime(i) == True:
            ll.remove(i)
    return ll    

def checks_if_prime(n):
    if n == 2:
    return True
    import math
    for i in range(math.ceil(0.5*n), 1, -1):
        if n % i == 0:
            return False
        elif i == 2:
            return True

print(final_lcm([1,2,3,4,5,6,7,8,9]))

Kindly pardon my poor choice of variables, I request you to see if the logic is correct and that the code is functional.

The syntax error which I am getting is that "factors" is invalid syntax though I don't agree with this. Please tell me where my code is wrong.

3
  • 4
    You should look into Euclid's algorithm: computing LCMs via prime factorizations is unnecessarily slow and complicated. Commented May 15, 2016 at 12:00
  • prime_thelist = list(set(thelist) - set(returns_new_thelist(previous_thelist)) - missing bracket for list(..). prime_thelist = list(set(thelist) - set(returns_new_thelist(previous_thelist))) Commented May 15, 2016 at 12:01
  • 7
    There's a new answer to your question showing a built-in solution that applies as of python 3.9. Please consider marking it as accepted so that new users who find your question can see that answer first (if they are using an older python version they can scroll down for the older answers). Commented Aug 17, 2020 at 11:15

21 Answers 21

59

This is the best way that I know of :

from math import gcd
a = [100, 200, 150]   #will work for an int array of any length
lcm = 1
for i in a:
    lcm = lcm*i//gcd(lcm, i)
print(lcm)

Hope this helps. All queries, contributions and comments are welcome :)

7
  • One of these geeksforgeeks.org/gcd-in-python . Most probably the 3rd one. Commented Jul 6, 2020 at 15:38
  • 1
    You can initialize lcm as 1 and then enumerate through all integers in a, thus avoid the slicing.
    – Escape0707
    Commented Sep 22, 2020 at 7:55
  • True, but with slicing I can reduce an unnecessary run of the loop. Commented Mar 28, 2021 at 20:40
  • 3
    Nvm, as @Hamza noted, we already have math.lcm in Python 3.9. And it handles lcm(0, 0) better than selected and the second upvoted answer. 🎉
    – Escape0707
    Commented Mar 29, 2021 at 3:31
  • 1
    I timed the program with and without slicing and the without slicing was faster. Updated. Thanks! Commented Mar 29, 2021 at 18:50
35

As of Python 3.9 lcm() function has been added in the math library. It can be called with the following signature:

math.lcm(*integers)

Return the least common multiple of the specified integer arguments. If all arguments are nonzero, then the returned value is the smallest positive integer that is a multiple of all arguments. If any of the arguments is zero, then the returned value is 0. lcm() without arguments returns 1.

Advantages:

  1. Besides being native,
  2. Its a one-liner,
  3. Its fastest,
  4. Can deal with arbitrarily long list of integers
  5. And can deal with nearly any kind of exceptions (e.g. lcm(0,0)) overlooked by custom-built solutions.
23

Works with an arbitrarily long denominator list.

from math import gcd # Python versions 3.5 and above
#from fractions import gcd # Python versions below 3.5
from functools import reduce # Python version 3.x

def lcm(denominators):
    return reduce(lambda a,b: a*b // gcd(a,b), denominators)

Example:

>>> lcm([100, 200, 300])
600
1
  • 2
    This is the only sane solution given the simplicity of the problem.
    – lyomi
    Commented Jul 23, 2018 at 19:07
11

In Numpy v1.17 (which is, as of writing, the non-release development version) there is an lcm function that can be used for two numbers with, e.g.:

import numpy as np
np.lcm(12, 20)

or for multiple numbers with, e.g.:

np.lcm.reduce([40, 12, 20])

There's also a gcd function.

3
  • 1
    I think this is the way to go now - instead of reinventing the wheel, just use the power of libraries. Not everything is a programming excercise. Commented Dec 12, 2019 at 8:32
  • Also, if you try to reduce an empty list, you get a not too clear error message: TypeError: No loop matching the specified signature and casting was found for ufunc lcm Commented Dec 12, 2019 at 8:37
  • 6
    Be aware that np.lcm.reduce([ list ]) does not work correctly if the LCM is a long. For example, np.lcm.reduce([2028, 5898, 4702]) gives the answer 391807628, which is not correct (tested using the most recent Anaconda distributions for Python 2.7 and 3.7). Using [2028L, 5898L, 4702L] works in Python 2.7 but I don't know of a solution in Python 3.
    – K. Morgan
    Commented Dec 12, 2019 at 14:12
5

Your solution might be too lengthy ... Try this !

from functools import reduce    # need this line if you're using Python3.x

def lcm(a, b):
    if a > b:
        greater = a
    else:
        greater = b

    while True:
        if greater % a == 0 and greater % b == 0:
            lcm = greater
            break
        greater += 1

    return lcm

def get_lcm_for(your_list):
    return reduce(lambda x, y: lcm(x, y), your_list)

ans = get_lcm_for([1, 2, 3, 4, 5, 6, 7, 8, 9])
print(ans)
2
  • Sir, can you please forward a proper guide on how to use this lambda function?
    – user6025181
    Commented Aug 20, 2017 at 6:09
  • 1
    You don't even need a lambda here. Just write: return reduce(lcm, your_list) instead.
    – Fränki
    Commented Aug 23, 2019 at 6:22
4

if you don't want to import anything.

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

A = [10, 25, 37, 15, 75, 12]

lcm = 1
for i in A:
    lcm = lcm * i // gcd(lcm, i)
    
print(lcm)
2

You're missing a closing parenthesis ()) in the third line. Hence the error in line factors.

Moreover in second to last line of your first function, you've named the variable factor instead of factors.

1

To find LCM of given list of numbers

def findDivisor(num):
    # 2,3 are the most common divisor for many numbers hence I go by divisor of 2,3
    # if not then by the same number as divisor
    if num%2 == 0:
        return 2
    elif num%3==0:
        return 3
    return num

def findLCM(lcmArray):
    lcm = 1
    while len(lcmArray) > 0:
        minOfLCMArray = min(lcmArray)
        divisor = findDivisor(minOfLCMArray)        

        for x in xrange(0, len(lcmArray)):
            Quotient = lcmArray[x]/divisor
            Reminder = lcmArray[x]%divisor
            if Reminder == 0:
                lcmArray[x] = Quotient

        lcm*=divisor
        minOfLCMArray = min(lcmArray)
        if minOfLCMArray == 1:
            lcmArray.remove(minOfLCMArray)
    return lcm

lcmArray = map(int, raw_input().split())
print findLCM(lcmArray)
1

A faster approach without using any math functions would be to calculate GCD and calculate LCM.

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

Now find LCM using GCF

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

Extend this to work with list as below

LCM = functools.reduce(lambda x, y: lcm(x, y), your_list_to_find_lcm)
1

I had written a code to find lcm of numbers within a list. The User can input any number of values he wants. I'm attaching the code below, It is simpler than the code you posted. Try checking this... I know your question is to find errors in your code, but try checking this for future purpose.

a = list(map(int,input('enter numbers for the lcm: ').strip().split()))
a.sort(reverse = True)
a
x = a[0]

while 1:
    sum = 0
    for i in a:
        if x%i == 0:
            sum += 1
    if sum == len(a):
        break
    else :
        x += 1
print(x,' is the lcm of numbers in the input')
0
c=1
i=0
q=0
j=2;
flag=0;
count=0;
a=input("ente 3 no")


a=a.split(',')
print(len(a))
for i in range(len(a)):
    z=int(a[i])
    c=c*z

while(j<c):
 for p in range(len(a)):

   if(j%int(a[p])==0):
       count=count+1

       if(count==len(a)):
           print('in count counter',count)    
           print('in count',j)        
           flag=1
           break
       else:

           flag=0
   else:
       break
 if(flag==1):
      print('flag',j)        
      break
 else:
           count=0
           j=j+1    

print(j)enter code here
print("count",count)
1
  • 2
    Please consider adding a short explanation to accompany your solution. Especially with longer snippets, it's sometimes hard to spot the differences between answers and the original. Commented Jul 30, 2018 at 18:41
0

Find LCM and GCD of a list of numbers

After reading all these solutions it is still unclear so, here is my possible simplest approach :)

find LCM using GCD

from fractions import gcd
from functools import reduce
a = [2,4] #given list
def LCM(a, b):
    return (a*b)//gcd(a,b) # as LCM(a,b)*GCD(a,b) = a*b
lcm = reduce(LCM, a) #here reduce will iterate through all 
                     #the elements one by one
gcd = reduce(gcd, a)

print(lcm, gcd)

OUTPUT:

4 2
0

if you do not wish to use GCD algorithm, below code returns the smallest multiple of the greatest number of the array:

            a=[5,10,15,7]
            ctr=1
            LCM=max(a)
            remList=[LCM%i for i in a]
            if all(v == 0 for v in remList):
                    print("LCM is : ", max(a))
            else:
                while True:
                    remList=[LCM%i for i in a]
                    if all(v == 0 for v in remList):
                        print("LCM is : ",LCM)
                        break
                    else:
                       LCM=LCM+max(a)
0

This may be useful to you, Rather finding LCM directly, it is a bit simpler to derive LCM from GCD. 

def gcd(a,b):
  if a == 0:
    return b
return gcd(b % a, a)
    
    
x=int(input("enter x"))
y=int(input("enter y"))
    
print(int(gcd(x,y)))
print(int((x*y)/gcd(x,y)))
0
prime_thelist = list(set(thelist) - set(returns_new_thelist(previous_thelist))

You're missing a bracket at the end of the line. Correct it to the following:

prime_thelist = list(set(thelist) - set(returns_new_thelist(previous_thelist)))

Also,

if n == 2:
return True

You need to indent the return statement because it is inside a conditional statement.

And it is generally best practice to import any libraries you might need at the beginning rather than in the middle of a function.

0
from math import gcd
a = [100, 200, 150]   #will work for an int array of any length
lcm = a[0]
for i in a[1:]:
    lcm = lcm*i//gcd(lcm, i)  
print lcm
0

I needed a 0 dependency one for python2.7 so I came up with this brute one:

def lcm(lst):
    """
    finds the lcm for the numbers in the list
    """

    candidate = max(lst)

    while True:
    
        if sum([candidate % i == 0 for i in lst]) == len(lst):
             return candidate

        candidate+=1
0

LCM for N numbers without using GCD

n=list(map(int,input().split()))
def LCMof2(n1,n2):
  m= max(n1,n2)
  while(1):
    if (m%n1==0 and m%n2==0):
      ans=m
      break
    m+=1
  return ans
lcm1=LCMof2(n[0],n[1])
for i in range(2,len(n)):
  ans=LCMof2(lcm1,n[i])
  lcm1=ans 
print(ans)
1
  • Sample Input : 1 2 3 4 5 Sample Output : 60
    – Mogith
    Commented Aug 9, 2022 at 18:43
-1

This is my answer to compute GCD and LCM. Please try it. Easiest one I could do.

import math
GCF = yourlist[0]
LCM = yourlist[0]
for i in yourlist[1:]:
    GCF = math.gcd(GCF, i)
LCM = LCM*i//math.gcd(LCM, i)
print(GCF)
print(LCM)
-1

This would be a good way to find lcm of a list of numbers in Python

from math import gcd
from functools import reduce

def lcm(a,b):
    gc = gcd(a, b) # gcd_of_two_numbers
    lc = (a*b) // gc
    return lc

numbers = [150, 200, 300]
result = reduce(lcm, numbers)
print(result)
1
  • 2
    Welcome to stackoverflow! When answering a question, consider adding more explanations about your code.
    – user14520680
    Commented Nov 3, 2020 at 18:39
-1

Simple solution to find LCM without using build-in gcd function

def gcd(x,y):
    while y:
         x,y = y,x%y
    return x

for i in ls:
    lcm = (lcm*i) // gcd(lcm,i)

print(lcm)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.