LCM (Least Common Factor).
The Least Common Multiple (LCM) is the smallest positive integer that is divisible by each of the given integers. In simpler terms, it's the smallest number that both numbers divide into evenly.
Let's understand with an example: Find LCM of 4 and 5.
- Multiple of 4 are: 4, 8, 12, 16, 20, 24, ...
- Multiple of 5 are: 5, 10, 15, 20, 25, 30, ...
The smallest number that appears in both lists is 20. Therefore, the LCM of 4 and 5 is 20.
This is one of the methods of finding the LCM of two numbers similarly there are many and we will learn all of them now with Python code.
Method 1: Find LCM Using Loop.
This approach involves finding the LCM through an iterative process using a loop. It starts with the larger of the two numbers and increments until a common multiple is found.
Algorithm:
- Initialize a variable (greater) with the maximum of the two numbers.
- Use a while loop to iterate until a common multiple is found.
- Check if both numbers are divisible by the current value of greater.
- If yes, the current value of greater is the LCM.
Python Code:
# Function to find LCM of two numbers def find_lcm(a, b): greater = max(a, b) while True: if greater % a == 0 and greater % b == 0: lcm = greater break greater += 1 return lcm num1 = 4 num2 = 5 result = find_lcm(num1, num2) print(f"The LCM of {num1} and {num2} is {result}")
The LCM of 4 and 5 is 20
Method 2: Find LCM Using GCD (Greatest Common Factor).
This approach utilizes the relationship between LCM and GCD. The formula is LCM(a, b) = |a * b| / GCD(a, b).
Algorithm:
- Import the math module of Python.
- Use the math.gcd() function to find the GCD of the two numbers.
- Calculate LCM using the above formula.
Python Code:
# Python code to find LCM of two numbers import math def find_lcm(a, b): return abs(a * b) // math.gcd(a, b) # Numbers to find LCM num1 = 12 num2 = 13 result = find_lcm(num1, num2) print(f"The LCM of {num1} and {num2} is {result}")
Output:
The LCM of 12 and 13 is 156
Method 3: Find LCM Using Prime Factors.
This approach leverages the prime factorization of numbers. The LCM is found by combining the prime factors of both numbers with the maximum occurrence.
Algorithm:
- Define a helper function to find prime factors.
- Use Counter to get the occurrence of prime factors for each number.
- Combine the prime factors with the maximum occurrence.
- Calculate LCM using the product of prime factors.
Python Code:
# Python code to find LCM using Prime Factors from collections import Counter def find_lcm(a, b): def prime_factors(n): i = 2 factors = [] while i * i <= n: if n % i: i += 1 else: n //= i factors.append(i) if n > 1: factors.append(n) return factors factors_a = Counter(prime_factors(a)) factors_b = Counter(prime_factors(b)) # Combine prime factors with maximum occurrence all_factors = factors_a | factors_b # Calculate LCM using prime factors lcm = 1 for factor, count in all_factors.items(): lcm *= factor ** count return lcm # Example usage: num1 = 5 num2 = 6 result = find_lcm(num1, num2) print(f"The LCM of {num1} and {num2} is {result}")
Output:
The LCM of 5 and 6 is 30
These are the three different ways of finding the LCM of two numbers, you can use any one of them based on your understanding and requirement to solve coding problems in Python.
No comments:
Post a Comment