How to Find GCD of Two Numbers in Python?

🤔Find GCD Of Two Numbers In Python Using Recursion

Recursion is a memory-intensive Python function that uses self-referential expression to call itself. To return the number's greatest common divisor, the function will keep calling and repeating itself until the predetermined condition is satisfied.

📚Algorithm

Step 1: Take two user inputs, x and y.

Step 2: Pass the inputs as arguments to the recursive function.

Step 3: If the second number equals zero, it returns the first number.

Step 4: Else, recursively call the function with the second parameter as an argument until it gets the remainder, which divides the second parameter by the first.

🧑‍💻Code

# The math module contains the gcd function
import math


#Calculating the gcd of 2 numbers.
def gcd(x,y):
    if y == 0:
        return x
    else:
        return gcd(y,x%y)
        
x=10
y=18
print(f"The computed GCD of {x} and {y} is {gcd(100,3)}."

You can also try this code with Online Python Compiler

Run Code

Output

🤔Find GCD Of Two Numbers In Python Using Loops

🧑‍💻Code

# The math module contains the gcd function
import math


#Calculating the gcd of 2 numbers.
x = 86
y = 44
n = min(x,y)


gcd = 0
for i in range(1,n+1):
    if x%i == 0 and y%i == 0:
        gcd = i
        
print(f"The computed GCD of {x} and {y} is {gcd}.")

You can also try this code with Online Python Compiler

Run Code

Output

Because the H.C.F. (highest common factor) of two numbers always lies between 1 and the minimum, the variable n saves the minimum value of x and y. Due to the for loop's exclusive use of n+1, it will execute for n+1 times. Verify that both values may be divided by the current value at each step.  If the current value of the for loop divides both values, the current value of the for loop will be hcf. The H.C.F. (highest common factor) of x and y will be returned after completing the loop successfully.

You can try it on online python compiler.

🤔Find GCD Of Two Numbers In Python Using Euclidean Algorithm

Euclid's algorithm is the most effective way to determine the gcd of two numbers in python. The method that divides a larger integer into smaller ones and subtracts the residue is the oldest one. The method divides the larger integer more from the residual and then repeats this process until the remaining equals zero.

For example, suppose we want to calculate the GCD of two numbers, 60 and 50. Then we divide the 60 by 50; it returns the remainder of 10. Now we divide the number 50 by 10, returning the remainder of 0. So, in this way, we get the GCD is 10.

📚Algorithm

Step 1: Two integer numbers, such as x and y.

Step 2: if x = 0, then the GCD(x, y) is y.

Step 3: if x = 0, the GCD(x, y) is x.

Step 4: x mod y find the remainder R.

Step 5: Suppose x = y and y = R

Step 6: Repeat steps 4 and 3 until x mod y equals or exceeds 0.

🧑‍💻Code

#The math module contains the gcd function
import math
#Calculating the gcd of 2 numbers.
x = 86
y = 44

while y:
    x,y = y, x%y

print(f"The computed GCD is {x}.")

You can also try this code with Online Python Compiler

Run Code

Output

So that’s all the possible techniques to find the gcd of two numbers in python. Before moving to the end of the article, let’s see some of the frequently asked questions to brush up on your knowledge. 
Check out this problem - First Missing Positive 

Frequently Asked Questions

Is gcd a built-in Python function?

You can use the built-in gcd function in Python's math module.

What are the methods to find the GCD of two numbers using python?

Some methods to find GCD are the Prime factorization method, the Long division method, and Euclid's division algorithm.

What purpose does GCD serve?

GCD function returns the largest common divisor of two or more integers. The biggest integer that divides numbers 1 and 2 without a remainder is known as the greatest common divisor.

Is GCD always positive?

A pair of integers' greatest common divisor (gcd) and their absolute values' gcd are the same. As a result, the function can swap out negative numbers for their positive negatives.

Can we efficiently find GCD of two numbers using python?

The Euclidean algorithm, often known as Euclid's algorithm, is an effective way to determine the greatest common divisor (GCD), or the biggest number that divides two integers (numbers) evenly without leaving a remainder.

Conclusion

To summarize, we explored different techniques to calculate the GCD of two numbers along with their algorithms and code. This concludes the article, and we hope you found it helpful.

Recommended Readings:

• Fibonacci Series in Python
• GCD Euclidean Algorithm
• Floor Division in Python
• Swapcase in Python