Greatest common divisor (GCD) and Lowest Common Multiple (LCM) of two input numbers

a=int(input("Enter first number:"))
b=int(input("Enter second number:"))

def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b,a%b)

GCD=gcd(a,b)
print("GCD is: ",GCD)

Output

Enter first number:85
Enter second number:20
GCD is:  5

Using Euclidean algorithm

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

# Example usage
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

print("The GCD of", num1, "and", num2, "is", get_gcd(num1, num2))

The Euclidean algorithm repeatedly replaces the larger number by the remainder of dividing the larger number by the smaller number until the remainder is zero. The last non-zero remainder is the GCD of the two numbers.

This implementation does not require importing any modules and gives us a deeper understanding of how GCD calculation works under the hood.

Using built-in math module

import math

def get_gcd(x, y):
    return math.gcd(x, y)

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

print("The GCD of", num1, "and", num2, "is", get_gcd(num1, num2))

Math module

Lowest Common Multiple (LCM)

The Lowest Common Multiple (LCM) of two integers is the smallest positive integer that is divisible by both of these numbers without leaving a remainder.

Without using the Math module
We can define our own function to compute the Greatest Common Divisor (GCD) first.

The LCM can be calculated by dividing the product of the two numbers by their GCD.

def get_gcd(x, y):
    while y:
        x, y = y, x % y
    return x # GCD of two numbers 

# Function to compute LCM using the GCD
def get_lcm(x, y):
    lcm = abs(x*y) // get_gcd(x, y)
    return lcm

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

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

Output

Enter first number: 20
Enter second number: 12
The LCM of 20 and 12 is 60

LCM using math module

import math

# Function to compute LCM
def get_lcm(x, y):
    return abs(x*y) // math.gcd(x, y)

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

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

Learn more about recursive functions here.
All Sample codes Strong Number Armstrong Number

All String methods casefold() string to lowercase Python- Tutorials

Subhendu Mohapatra

Author & Instructor at plus2net

I write and maintain practical tutorials on Python, PHP, SQL, JavaScript, HTML, jQuery, and web development at plus2net. The tutorials focus on clear explanations, working examples, and code that readers can test and adapt while learning.

About the author Watch on YouTube

Connect:

Subscribe to our YouTube Channel here