Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two numbers is defined as the highest divisor that can divide both the given numbers completely.
For example, let's take two numbers 84 and 56.
The highest number that can divide both the given number is completely is 28
84 % 28 == 0
56 % 28 == 0
So GCD of two numbers is 28
Least Common Multiple (LCM) is defined as a number which is divisible by two or more given number
Again for LCM Lets take example two numbers 84 and 56.
168 % 84 == 0
168 % 56 == 0
So LCM of two numbers is : 168
Write a Python Program to Compute GCD LCM of Two Numbers Using Functions
Define a function named as find gcd and pass the two numbers that are a and b to the function as argument. using the euclidean algorithm use while loop until b is not equals to zero,
Set the values of a as b and b value changes to a modulus b. keep modulating the value of B until the value of b becomes zero and once the value becomes zero return the value of a as the gcd of a and b
def find_gcd(a, b):
while b != 0:
a, b = b, a % b
return a
Define a function that is find_lcm and pass the two input arguments as numbers a and b, take the max of two numbers that are a and b using the if statement.
Once we get the max of two numbers a and b, Use the infinite while loop and try to divide Max number with the A and B value, using the modulus operation. if you find a max number that can divide both A and B together at the same time you have found that LCM of a and b. Else keep incrementing the max value until you find the LCM.
def find_lcm(a, b):
max = a if a > b else b
while True:
if max % a == 0 and max % b == 0:
return max
max += 1
Let's take two variables first and second and ask a user to enter the two numbers using input function call and then convert them to integers using the type conversion int() function call.
first = int(input("Enter First Number : "))
second = int(input("Enter Second Number : "))
Using the print function call directly print the the user friendly message gcd of two numbers and LCM of two numbers and directly call the two functions find_lcm and find_gcd inside the print statement by passing first and second values to it as shown below
print("GCD of two numbers is : ", find_gcd(first, second))
print("LCM of two numbers is : ", find_lcm(first, second))
Complete Program
==================================
def find_lcm(a, b):
max = a if a > b else b
while True:
if max % a == 0 and max % b == 0:
return max
max += 1
def find_gcd(a, b):
while b != 0:
a, b = b, a % b
return a
first = int(input("Enter First Number : "))
second = int(input("Enter Second Number : "))
print("GCD of two numbers is : ", find_gcd(first, second))
print("LCM of two numbers is : ", find_lcm(first, second))
OUTPUT
====================
Enter First Number : 11
Enter Second Number : 22
GCD of two numbers is : 11
LCM of two numbers is : 22
OUTPUT
=====================
Enter First Number : 84
Enter Second Number : 56
GCD of two numbers is : 28
LCM of two numbers is : 168
OUTPUT
====================
Enter First Number : 900
Enter Second Number : 99
GCD of two numbers is : 9
LCM of two numbers is : 9900
Conclusion
===================
Try executing the above program by providing the random input values as a two numbers to the program note down the values
Comment down below if you have any suggestions to improve the above program
0 Comments