Python program to Compute the GCD and LCM of two integer

Oct 22, 2021

Write a Python program to Compute the greatest common divisor (GCD) and least common multiple (LCM) of two integer

This python program allows the user to enter two positive integer values and compute GCD using while loop. Next, python program calculate LCM of two positive integer values using GCD.

What is Greatest common Divisior (GCD)?

In Mathematics, the Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides given integer values. For example, the GCD value of integer 8 and 12 is 4 because both 8 and 12 are divisible by 1, 2, and 4 (the remainder is 0), and the largest positive integer among them is 4.

The Greatest Common Divisor (GCD) is also known as Highest Common Factor (HCF), or Greatest Common Factor (GCF), or Highest Common Divisor (HCD), or Greatest Common Measure (GCM).

What is Least Common Multiple(LCM)?

In Mathematics, the Least Common Multiple (LCM) of two or more integers is the smallest positive integer that is totally divisible by the given integer values.Remainder should be zero after division. For example, the LCM value of integer 2 and 3 is 12 because 12 is the smallest positive integer that is divisible by both 2 and 3 (the remainder is 0).

The least common multiple is also known as lowest common multiple, or smallest common multiple of two integers.

Below is source code

# python program to find LCM of two number using GCD

#input two numbers
n1 = int(input("Enter First number :"))
n2 = int(input("Enter Second number :"))
x = n1
y = n2
while(n2!=0):
t = n2
n2 = n1 % n2
n1 = t
gcd = n1
print("GCD of {0} and {1} = {2}".format(x,y,gcd))
lcm = (x*y)/gcd
print("LCM of {0} and {1} = {2}".format(x,y,lcm))

Output:

>> %Run gcdlcm.py
Enter First number :54
Enter Second number :24
GCD of 54 and 24 = 6
LCM of 54 and 24 = 216.0

>>> %Run gcdlcm.py
Enter First number :4
Enter Second number :6
GCD of 4 and 6 = 2
LCM of 4 and 6 = 12.0

>>> %Run gcdlcm.py
Enter First number :125
Enter Second number :25
GCD of 125 and 25 = 25
LCM of 125 and 25 = 125.0

Explaination:

This python program allows the user to enter two positive integer values n1 and n2. We declared two variables x and y and assigned value of n1 and n2 to them. We used while loop to check the remainder of n1 % n2 and n2 is equals to zero or not. If true, n1 is calculated. After that, value of n1 is assigned to GCD. With the help of GCD, we can calculate LCM of two integer. Here We used mathematical formula to calculate LCM.

First,we multiplied two positive integers and then divided by gcd to compute LCM of two integer.

<