# Python Program for LCM Of Two Numbers

## LCM of two numbers in Python

Here, in this section we will discuss the LCM of two numbers in python.
In this Python Program find the LCM of Two Numbers which numbers are entered by the user. Basically the LCM of two numbers is the smallest number which can divide the both numbers equally. This is also called Least Common Divisor or LCD.

### We will learn

• Method 1: A linear way to calculate LCM
• Method 2: Modified interval Linear way
• Method 3: Simple usage of HCF calculation to determine LCM
• Method 4: Repeated subtraction to calculate HCF and determine LCM
• Method 5: Recursive repeated subtraction to calculate HCF and determine LCM
• Method 6: Modulo Recursive repeated subtraction to calculate HCF and determine LCM

### Method 1

#### Algorithm

For a input num1 and num2. This method uses two following observations –

• LCM of two numbers will at least be equal or greater than max(num1, num2)
• Largest possibility of LCM will be num1 * num2

When iterating in (i) We can linearly find an (i) that is divisible by both num1 & num2

### Method 1 : Python Code

Run
```num1 = 12
num2 = 14
for i in range(max(num1, num2), 1 + (num1 * num2)):
if i % num1 == i % num2 == 0:
lcm = i
break
print("LCM of", num1, "and", num2, "is", lcm)
```

### Output

`LCM of 12 and 14 is 84`

### Method 2

#### Algorithm

For input num1 and num2. This method uses two following observations –

• Rather than linearly checking for LCM by doing i++. We can do i = i + max
• Starting with i = max (num1, num2)
• The next possibility of LCM will be ‘max’ interval apart

### Method 2 : Python Code

Run
```num1 = 12
num2 = 14
for i in range(max(num1, num2), 1 + (num1 * num2), max(num1, num2)):
if i % num1 == i % num2 == 0:
lcm = i
break

print("LCM of", num1, "and", num2, "is", lcm)

```

### Output

`LCM of 12 and 14 is 84`

### Method 3

#### Algorithm

• Initialize HCF = 1
• Run a loop in the iteration of (i) between [1, min(num1, num2)]
• Note down the highest number that divides both num1 & num2
• If i satisfies (num1 % i == 0 && num2 % i == 0) then new value of HCF is i
• Use lcm formula :- (num1*num2) / hcf
• Print the output

### Method 3 : Python Code

Run
```num1 = 12
num2 = 14

# Calculating HCF here
for i in range(1, max(num1, num2)):
if num1 % i == num2 % i == 0:
hcf = i

# LCM formula
lcm = (num1*num2)//hcf

print("LCM of", num1, "and", num2, "is", lcm)

```

### Output

`LCM of 12 and 14 is 84`

### Method 4

#### Algorithm

• Run a while loop until num1 is not equals to num2
• If num1>num2 then num1 = num1 – num2
• Else num2 = num2 – num1
• After the loop ends both num1 & num2 stores HCF
• Use LCM formula :- (num1*num2) / hcf
• Print Output

### Method 4 : Python Code

Run
```def getHCF(num1, num2):
while num1!=num2:
if num1>num2:
num1-=num2
else:
num2-=num1
return num1

num1 = 12
num2 = 14

# Calculating HCF here
hcf = getHCF(num1, num2)

# LCM formula
lcm = (num1*num2)//hcf

print("LCM of", num1, "and", num2, "is", lcm)

```

### Output

`LCM of 12 and 14 is 84`

### Method 5

#### Algorithm

• Checked whether any of the input is 0 then return sum of both numbers
• If both input are equal return any of the two numbers
• If num1 is greater than the num2 then Recursively call findHCF(num1 – num2, num2)
• Else Recursively call findHCF(num1, num2-num1)

### Method 5 : Python Code

Run
```# Recursive function to return HCF of two number
def getHCF(num1, num2):
# Everything divides 0
if num1 == 0 or num2 == 0:
return num1 + num2

# base case
if num1 == num2:
return num1

# num1>num2
if num1 > num2:
return getHCF(num1 - num2, num2)
else:
return getHCF(num1, num2 - num1)

num1 = 12
num2 = 14

# Calculating HCF here
hcf = getHCF(num1, num2)

# LCM formula
lcm = (num1*num2)//hcf

print("LCM of", num1, "and", num2, "is", lcm)
```

### Output

`LCM of 12 and 14 is 84`

### Method 6

#### Algorithm

This method uses recursion.

In Addition, we are using modulo operation to reduce the number of subtractions required and improve the time complexity

For this method, you need to know how to calculate HCF, check this post here

We use repeated Modulo Recursive subtraction (Euclidean Algorithm) to calculate the HCF.

### Method 6 : Python Code

Run
```def getHCF(a, b):
if b == 0:
return a
else:
return getHCF(b, a % b)

num1 = 12
num2 = 14
hcf = getHCF(num1, num2)

# LCM formula
lcm = (num1 * num2) // hcf
print("The hcf is :", lcm)
```

### Output

`LCM of 12 and 14 is 84`

### 3 comments on “Python Program for LCM Of Two Numbers”

• karalesamarth18

import math as m
num1 = int(input(‘Enter first number: ‘))
num2 = int(input(‘Enter second number: ‘))
HCF = m.gcd(num1,num2)
LCM = int((num1*num2)/(HCF))
print(‘LCM of given numbers: ‘, LCM)

x=int(input(“enter first number : “))
y=int(input(“enter second number : “))
def lcm(a,b):
if a>b:
bigger=a
else:
bigger=b
for i in range(bigger,(a*b)+1):
if i%a==0 and i%b==0:
lcm_of_num=i
break
return lcm_of_num
print(lcm(x,y))

• Sonal

num1=int(input(“Enter the 1st number”))
num1=int(input(“Enter the 2nd number”))
l=[]
for i in range(1,min(num1,num2)):
if (num1%i==0) and (num2%i==0):
l.append(i)
else:
continue
hcf=max(l)
lcm=(num1*num2)//hcf
print(“{} is the LCM of {} and {}”.format(hcf,num1,num2))