Skip to main content

How to Find the LCM and GCD of Two Numbers in Python

How to Find the LCM and GCD of Two Numbers in Python | Rustcode

How to Find the LCM and GCD of Two Numbers in Python

Finding the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers is a common need in mathematics, coding interviews, and real applications. Python provides both classic algorithms and handy built-in functions for this task. Here’s how you can quickly compute GCD and LCM for any two numbers with practical examples.

Table of Content

What Are GCD and LCM?

  • GCD (Greatest Common Divisor): The largest integer that divides both numbers exactly.
  • LCM (Least Common Multiple): The smallest positive integer that is a multiple of both numbers.
  • Relationship: a * b = GCD(a, b) * LCM(a, b)

01. Using Built-in Functions (math.gcd() and math.lcm() in Python 3.9+)

Python’s math module makes GCD and LCM calculations easy and efficient.

import math

a = 54
b = 24

# GCD: Available in Python 3.5+
gcd_value = math.gcd(a, b)

# LCM: Available in Python 3.9+
lcm_value = math.lcm(a, b)

print("GCD of", a, "and", b, "is:", gcd_value)
print("LCM of", a, "and", b, "is:", lcm_value)

Output:

GCD of 54 and 24 is: 6
LCM of 54 and 24 is: 216
Explanation:
  • math.gcd() is available in Python 3.5+ and works with any integers*.
  • math.lcm() is available in Python 3.9+ and can take two or more numbers.

* Use abs() if you want only positive results for negative numbers.

02. Using the Euclidean Algorithm for GCD

If you want to implement GCD yourself (for learning or in older Python versions), use the classic Euclidean algorithm:

def compute_gcd(x, y):
    while y:
        x, y = y, x % y
    return x

print(compute_gcd(54, 24))  # Output: 6
Explanation:
  • Fast and very reliable—this is how GCD is computed under the hood.

03. Calculating LCM Using the GCD Formula

You can easily compute LCM using the relationship between GCD and LCM:

def compute_lcm(x, y):
    return abs(x * y) // compute_gcd(x, y)

print(compute_lcm(54, 24))  # Output: 216
Explanation:
  • abs(x * y) // GCD(x, y) is mathematically guaranteed to yield the LCM for any integers (except when one is zero).

04. Custom GCD and LCM Function with User Input

Here’s a robust example that computes both, using functions and user input:

from math import gcd

def lcm(x, y):
    if x == 0 or y == 0:
        return 0
    return abs(x * y) // gcd(x, y)

n1 = int(input("Enter first number: "))
n2 = int(input("Enter second number: "))

gcd_result = gcd(n1, n2)
lcm_result = lcm(n1, n2)

print(f"GCD of {n1} and {n2} is: {gcd_result}")
print(f"LCM of {n1} and {n2} is: {lcm_result}")

Sample Output:

Enter first number: 54
Enter second number: 24
GCD of 54 and 24 is: 6
LCM of 54 and 24 is: 216
Explanation:
  • Handles user input safely and computes both values efficiently.
  • Returns 0 for LCM if either number is 0 (as per standard definition).

05. Comparison Table: Methods

Method GCD LCM Requires Python Version Best For
math.gcd, math.lcm Yes Yes 3.9+ for math.lcm Quick, built-in, reliable
Euclidean algorithm Yes With formula Any Learning, legacy code
Custom user input function Yes Yes Any Reusable programs

Conclusion

To find the LCM and GCD of two numbers in Python, use math.gcd() and math.lcm() for simplicity and speed. For greater compatibility, implement the Euclidean algorithm for GCD and use the formula LCM = abs(a * b) // GCD(a, b). These techniques are accurate, efficient, and widely applicable to any problem involving divisors or multiples.

Comments

Post a Comment