Find LCM of two numbers

Question

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 =[1]
    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.

Answer 1

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).