# Find LCM of two numbers

The problem is to find LCM of two numbers. I have tried to solve the problem in two ways. First by using the LCM formula :

LCM (a,b)= a*b/GCD(a,b).


Second, by finding out the multiples of each number and then finding the first common multiple. Below are the codes that I have written:

### Code 1:

#Using the LCM formula LCM = a*b / gcd(a,b)
def LCM(x , y):
""" define a function LCM which takes two integer inputs and return their LCM using the formula LCM(a,b) = a*b / gcd(a,b) """
if x==0 or y == 0:
return "0"

return (x * y)/GCD(x,y)

def GCD(a , b):
""" define a function GCD which takes two integer inputs and return their common divisor"""
com_div =
i =2
while i<= min(a,b):
if a % i == 0 and  b % i ==0:
com_div.append(i)
i = i+1
return com_div[-1]

print LCM(350,1)
print LCM(920,350)


### Code 2:

#Finding the multiples of each number and then finding out the least common multiple
def LCM(x , y):
""" define a function LCM which take two  integerinputs and return their LCM"""
if x==0 or y == 0:
return "0"
multiple_set_1  = []
multiple_set_2  = []
for i in range(1,y+1):
multiple_set_1.append(x*i)
for j in range(1,x+1):
multiple_set_2.append(y*j)
for z in range (1,x*y+1):
if z in multiple_set_1:
if z in multiple_set_2:
return z
break

print LCM(350,450)


I want to know which one of them is a better way of solving the problem and why that is the case. Also suggest what other border cases should be covered.

## 1 Answer

About Version 1:

GCD(a, b) has a time complexity of $O(min(a, b))$ and requires an array for intermediate storage. You could get rid of the array by iterating over the possible divisors in reverse order, so that you can early return if a common divisor is found.

About Version 2:

LCM(x , y) has a time complexity of $O(xy)$ and requires two arrays for intermediate storage, so this worse than version 1. You could improve this by pre-computing only the multiples of one number, and then test the multiples of the other number (in reverse order) until you find a common multiple, and then early return.

Common issues:

• LCM should always return a number, your code returns the string "0" in some cases.

• Both functions take integer arguments (according to the docstring ) but do not produce sensible results for negative input.

• The usage of whitespace in your code is inconsistent. Examples:

if x==0 or y == 0:
i =2

• More PEP8 coding style violations (most of them related to spacing) can be detected by checking your code at PEP8 online.

A better algorithm

The "Euclidean Algorithm" is a well-known method for computing the greatest common divisor, and superior to both of your approaches.

It is already available in the Python standard library:

>>> from fractions import gcd   # Python 2
>>> from math import gcd        # Python 3
>>> gcd(123, 234)
3


This should be used as the basis for implementing an LCM function.

Have a look at https://rosettacode.org/wiki/Greatest_common_divisor#Python, if you want to implement the GCD yourself (for educational purposes), for example

def gcd_iter(u, v):
while v:
u, v = v, u % v
return abs(u)


This is short, simple, needs no additional space, and fast: the time complexity is (roughly) $=O(\log(max(a, b))$ (see for example What is the time complexity of Euclid's Algorithm).