Python code to find LCM

Introduction: The Least Common Multiple (LCM) of two numbers is the smallest number that is a multiple of both. LCM is used in various mathematical operations like simplifying fractions, addition and subtraction of fractions, etc. In this blog, we will learn how to write a Python program to find the LCM of two given numbers.

Step 1: Understanding LCM

To find the LCM of two numbers, we need to understand the concept of factors and multiples. A factor of a number is a number that divides the given number without leaving a remainder. For example, 3 is a factor of 9 because 9 ÷ 3 = 3 with no remainder. A multiple of a number is a number that can be obtained by multiplying the given number with any other number. For example, 12 is a multiple of 3 because 3 × 4 = 12.

The LCM of two numbers is the smallest number that is a multiple of both the numbers. For example, the LCM of 6 and 8 is 24, which is the smallest number that is a multiple of both 6 and 8.

Step 2: Finding LCM using prime factorization method

One of the most efficient methods to find LCM of two numbers is prime factorization method. In this method, we need to first factorize both the numbers into prime factors, and then find the product of all prime factors with their highest power.

For example, let’s find the LCM of 24 and 36 using prime factorization method:

24 = 2 × 2 × 2 × 3 36 = 2 × 2 × 3 × 3

Now, we take all the prime factors and their highest power:

2^3 × 3^2 = 72

Therefore, the LCM of 24 and 36 is 72.

Step 3: Writing Python code to find LCM

Now that we understand the concept of LCM and how to find it using prime factorization method, let’s write a Python program to find the LCM of two given numbers.

def find_lcm(x, y):
    # 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

num1 = 24
num2 = 36

print("The LCM of", num1, "and", num2, "is", find_lcm(num1, num2))

In this program, we first determine which number is greater, and then we start from the greater number and check if it is divisible by both the given numbers. If it is, we have found the LCM and we return it. If it’s not, we increment the greater number by 1 and continue the loop until we find the LCM.

Step 4: Testing the code

Let’s test our program by finding the LCM of two different sets of numbers:

Example 1:

num1 = 12

num2 = 18

Output: The LCM of 12 and 18 is 36

Example 2:

num1 = 5

num2 = 7

Output: The LCM of 5 and 7 is 35

Tags: algorithm, calculate, computation, example, LCM, math, method, program, python