Python program to find gcd(Greatest Common Divisor) of two numbers
GCD(Greatest Common Divisor) of two numbers is the largest number that divides both of them. Let's see how to find GCD of two numbers manually:
18 = 2 * 3 * 3
60 = 2 * 2 * 3 * 5
Now, multiply the common factors of both numbers
= 2 * 3
= 6
Python program to find GCD of two numbers:
def gcd(n1, n2):
if(n1 == 0):
return n2
if(n2 == 0):
return n1
while(n2 != 0):
if(n1 > n2):
n1 = n1 - n2
else:
n2 = n2 - n1
return n1
x=int(input("Enter first number:"))
y=int(input("Enter second number:"))
res = gcd(x, y)
print("\nGCD of {0} and {1} = {2}".format(x, y, res))
Results
Example #1:
Enter first number: 18
Enter second number: 60
GCD of 18 and 60 = 6
Example #2:
Enter first number: 0
Enter second number: 60
GCD of 0 and 60 = 60
Example #3:
Enter first number: 18
Enter second number: 60
GCD of 60 and 0 = 60