87

I am currently using a function that accepts two numbers and uses a loop to find the least common multiple of those numbers,

def lcm(x, y):
   """This function takes two
   integers and returns the L.C.M."""

   # Choose the greater number
   if x > y:
       greater = x
   else:
       greater = y

   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm

Is there a built-in module in Python that does it instead of writing a custom function?

0

6 Answers 6

114

In Python 3.8 and earlier

There is no such thing built into the stdlib.

However, there is a Greatest Common Divisor function in the math library. (For Python 3.4 or 2.7, it's buried in fractions instead.) And writing an LCM on top of a GCD is pretty trivial:

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

Or, if you're using NumPy, it's come with an lcm function for quite some time now.

2
97

In Python 3.9+

This is available as math.lcm(). It also takes any number of arguments, allowing you to find the lowest common multiple of more than 2 integers.

For example:

>>> from math import lcm
>>> lcm(2, 5, 7)
70
16

Try this instead:

def lcm(x, y):
    from fractions import gcd # or can import gcd from `math` in Python 3
    return x * y // gcd(x, y)
5
  • 4
    Why do you put the import in the function?
    – wjandrea
    Commented Jan 2, 2020 at 17:14
  • 1
    Why not? It's better to post a self-contained solution than to assume the user is fine with littering a containing scope with names (like "gcd") that are irrelevant to solving the problem at hand. If you want to move the import to a containing scope, that's fine.
    – Tim Peters
    Commented Jan 2, 2020 at 17:26
  • 13
    There is one disadvantage on having imports inside functions: Any missing module will only be discovered when such function is executed. Having all imports unconditionally at the top of a module makes sure all dependencies are available by the time the module is loaded. (Sure, this is not an issue for standard lib modules.) Commented Jan 5, 2020 at 14:43
  • 3
    ^^ Also, the import time might be expensive. It's generally advisable to pay the cost at module import time rather than function call.
    – anon01
    Commented Oct 15, 2020 at 9:32
  • 2
    @TimPeters I've understood that the module level __all__ is intended to advertise public names, and some extra names in containing scopes doesn't really harm anything. As for "why not", the style guide does say Imports are always put at the top of the file but I think the more important reason is for code to be up-front about their dependencies. That makes browsing a large code-base easier, and during testing it means mocking/patching a dependency from the module namespace is simpler.
    – wim
    Commented Nov 17, 2020 at 17:29
2

To simplify your code a little:

def lcm(x, y):
    for currentPossibleLCM in range(max(x,y), (x*y)+1)
         if((currentPossibleLCM % x == 0) and (currentPossibleLCM % y == 0)):
              return currentPossibleLCM

Runtime: O(x*y)

2

This is not only for two numbers specifically but for finding LCM of an array of integers. (without using math.lcm())

import math
from functools import reduce

def lcm(arr):

    l=reduce(lambda x,y:(x*y)//math.gcd(x,y),arr)
    return l
0

I've created this one for receiving an arbitrary number of parameters and thus calculate the lcm

from math import gcd, prod

def lcm(*list):
    return abs(prod(list)) // gcd(*list)

lcm(1,44,22)
1
  • Hey Juan, that code is not mathematically correct. E.g. when using values [4,6,8], it returns 96, while it should be 24.
    – QuadU
    Commented Aug 22 at 8:33

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.