Python program to find gcd of two numbers

Python program to find gcd of two numbers : In this tutorial we are going to explain the gcd of the numbers with the examples. The gcd is the “Greatest common Divisor” used in the mathematical operations. In mathematics gcd of two numbers are the not all zero and largest positive number that divide each of the number.
Example as:-
 The gcd of 8 and 12 is 4.
The gcd also known as the greatest common factor, highest common factor, highest common divisor etc.
In the gcd of two numbers the largest number is divided between them and the gcd of 20 and 15 is 5as the 5 number will divide 20 as well as 15 and no larger number property.
The gcd is used in the applications as the number theory for arithmetic such as the RSA and for simple applications as the fractions.

Steps:-

1. Taking two numbers from user.
2. Then pass two numbers as the argument to the recursive function.
3. If the second number will become 0 then return first number.
4. Else call the recursive function with argument as second number and the remainder when first number is divisible by second number.
5. Return the first number which us the gcd of two numbers.
6. Then print the gcd.
7. Exit the program.

Explanation:-

1. The user must enter the two numbers.
2. Then the numbers are passed as an argument to the recursive function.
3. If the second number becomes 0 then first number is returned.
4. Else the function is recursively called with argument as the second number and the remainder when first number is divided by the second number.
5. Then first number us returned called as gcd of two numbers.
6. The gcd is printed.

1) Program Using the recursion function:-

def hcfnaive (a, b):
if (b==0):
return a
else:
return hcfnaive (b, a%b)
a=60
b=48
print(“The gcd of 60 and 48 is:” end=””)
print(hcfnaive (60, 48))
Output:-
The gcd of 60 and 48 is: 12

2) gcd of two numbers in python using recursion

def computeGCD(x,y):
if x>y:
small=y
else
small=x
for i in range (1, small+1):
if((x%i==0) and(y%i==0)):
return gcd
a=60
b=48
print(“The gcd of 60 and 48 is:”end=””)
print(computeGCD (60, 48))
Output:-
The gcd of 60 and 48 is: 12

3) gcd of two numbers Using the Euclidean algorithm :-

def computeGCD(x, y):
while (y):
x, y=y, x%y
return x
a=60
b=48
print(“The gcd of 60 and 48 is: “, end=” ”)
Output:-
The gcd of 60 and 48 is: 12

4) gcd of two number Using the math.gcd () function of python:-

Using the gcd() function we can have same gcd with one line.
Parameters:-
x:-They are the non-negative integers whose gcd has computed.
y: - They are the non-negative integers whose gcd has computed.
Return:-
The method returns the positive integer value after the gcd of given parameter of x and y.
Exceptions are the x and y are 0 and function will return 0 if any number or the error is raised.
import math
print(“The gcd of 60 and 48 is:” end=””)
print(math.gcd (60, 48))
Output:-
The gcd of 60 and 48 is: 12