Python Program to Find LCM of Two Numbers

You can find the LCM of two numbers in Python by first finding their GCD using math.gcd() and then calculating LCM as abs(a*b) // gcd.

Examples

Inputa=4, b=6

Output12

Inputa=15, b=20

Output60

Inputa=7, b=3

Output21

How to Think About It

To find the LCM of two numbers, first find their greatest common divisor (GCD). The LCM is the smallest number that both input numbers divide evenly into. Using the relation LCM * GCD = product of the two numbers helps calculate LCM easily.

Algorithm

1

Get two input numbers a and b

2

Find the GCD of a and b

3

Calculate LCM as absolute value of (a multiplied by b) divided by GCD

4

Return or print the LCM

Code

python

import math

def find_lcm(a, b):
    gcd = math.gcd(a, b)
    lcm = abs(a * b) // gcd
    return lcm

# Example usage
num1 = 4
num2 = 6
print(find_lcm(num1, num2))

Output

12

Dry Run

Let's trace the example where a=4 and b=6 through the code

1

Calculate GCD

math.gcd(4, 6) returns 2

2

Calculate LCM

LCM = abs(4 * 6) // 2 = 24 // 2 = 12

3

Return LCM

Return 12 as the LCM

Step	Operation	Value
1	GCD of 4 and 6	2
2	LCM calculation abs(4*6)//2	12
3	Return LCM	12

Why This Works

Step 1: Find GCD first

The greatest common divisor (GCD) is the largest number that divides both inputs without remainder. We use math.gcd() to find it efficiently.

Step 2: Use relation between LCM and GCD

LCM and GCD relate by the formula LCM * GCD = |a * b|. This lets us find LCM easily once GCD is known.

Step 3: Calculate and return LCM

Divide the absolute product of the two numbers by the GCD to get the LCM, ensuring the result is positive.

Alternative Approaches

Using a loop to find LCM

python

def find_lcm_loop(a, b):
    max_num = max(a, b)
    lcm = max_num
    while True:
        if lcm % a == 0 and lcm % b == 0:
            return lcm
        lcm += 1

print(find_lcm_loop(4, 6))

This method is simple but slower for large numbers because it checks multiples one by one.

Using prime factorization

python

# This method involves finding prime factors of both numbers and combining them
# It is more complex and less efficient for beginners

Prime factorization is educational but not practical for quick LCM calculation.

Complexity: O(log(min(a,b))) time, O(1) space

Time Complexity

Finding GCD using Euclid's algorithm takes O(log(min(a,b))) time, which dominates the calculation. The rest is simple arithmetic.

Space Complexity

The program uses constant extra space for variables, so space complexity is O(1).

Which Approach is Fastest?

Using math.gcd() is fastest and most efficient compared to looping or prime factorization.

Approach	Time	Space	Best For
Using math.gcd()	O(log(min(a,b)))	O(1)	Efficient and simple for all inputs
Loop checking multiples	O(n) worst case	O(1)	Easy to understand but slow for large numbers
Prime factorization	Varies, usually slower	O(n) for factors	Educational, not practical for large inputs