Python: Compute LCM (Least Common Multiple)

1. Introduction

The least common multiple (LCM) of two numbers is the smallest number that is a multiple of both. It is a fundamental concept in number theory and is commonly used in problems involving fractions and modular arithmetic. In this blog post, we will create a Python program to compute the LCM of two numbers.

2. Program Overview

The program will:

1. Take two positive integers as input from the user.

2. Compute their LCM.

3. Display the LCM to the user.

To find the LCM of two numbers, we will use the following formula:

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

Where GCD stands for the greatest common divisor.

3. Code Program

# Function to compute the GCD using Euclidean algorithm
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

# Function to compute LCM using the formula
def lcm(x, y):
   return (x * y) // gcd(x, y)

# Taking two positive integers as input
num1 = int(input("Enter the first number: "))
num2 = int(input("Enter the second number: "))

# Calculating LCM
result = lcm(num1, num2)

# Displaying the LCM
print(f"The LCM of {num1} and {num2} is: {result}")

Output:

Enter the first number: 4
Enter the second number: 5
The LCM of 4 and 5 is: 20

4. Step By Step Explanation

1. We first define a helper function gcd to find the greatest common divisor of two numbers using the Euclidean algorithm.

2. Next, we define the lcm function that computes the LCM using the formula mentioned earlier. This formula exploits the relationship between the LCM and GCD.

3. The program takes two positive integers as input from the user using the input function.

4. The LCM of these two numbers is then calculated using the lcm function.

5. Finally, the result is displayed using the print function.

By understanding the relationship between LCM and GCD and using the efficient Euclidean algorithm, we can efficiently compute the LCM of two numbers.