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))
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))