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:
num1 = 12
num2 = 18
Output: The LCM of 12 and 18 is 36
num1 = 5
num2 = 7
Output: The LCM of 5 and 7 is 35
Follow us on Twitter: Hacktube5
Follow us on Youtube: Hacktube5