Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
📜Introduction
2.
🤔Find GCD of Two Numbers in Python Using gcd() Function.
2.1.
📚Syntax
2.1.1.
Parameters
2.1.2.
Return Type
2.2.
🧑‍💻Code
3.
🤔Find GCD Of Two Numbers In Python Using Recursion
3.1.
📚Algorithm
3.2.
🧑‍💻Code
4.
🤔Find GCD Of Two Numbers In Python Using Loops
4.1.
🧑‍💻Code
5.
🤔Find GCD Of Two Numbers In Python Using Euclidean Algorithm
5.1.
📚Algorithm
5.2.
🧑‍💻Code
6.
Frequently Asked Questions
6.1.
Is gcd a built-in Python function?
6.2.
What are the methods to find the GCD of two numbers using python?
6.3.
What purpose does GCD serve?
6.4.
Is GCD always positive?
6.5.
Can we efficiently find GCD of two numbers using python?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

How to Find GCD of Two Numbers in Python?

Author Mayank Goyal
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

📜Introduction

The mathematical term GCD (Greatest Common Divisor) describes finding the biggest common factor between two values. The greatest positive integer that divides two or more numbers that are not all zeros is called the GCD. H.C.F. is another name for GCD (Highest Common factor).

Example: There are two numbers, 5 and 10. What is the GCD/HCF of 5 and 10?

As we discuss the definition of GCD, it tells us the highest common factor or greatest common divisor that divides two numbers. In the case of 5 and 10, the highest common factor is 5.

We will be discussing the various methods to find the GCD of two numbers in python by using:

💡gcd() function

💡recursion

💡loops

💡Euclidean Algorithm


Must Recommended Topic, Floor Division in Python, Swapcase in Python

🤔Find GCD of Two Numbers in Python Using gcd() Function.

We can find GCD of two numbers in Python in several ways. Utilizing the math module's gcd() function is one of the techniques.

While using the gcd() function to find the gcd of two numbers in python, the math module must be imported. The math module will raise an import error if it is not imported.

📚Syntax

math.gcd(x, y)

Parameters

x: Non-negative integer passed as a first argument.

y: Non-negative integer passed as a second argument.

Return Type

The math will return the GCD of x and y, the highest common factor.

🧑‍💻Code

#The math module contains the gcd function
import math


#Calculating the gcd of 2 numbers.
x = 10
y = 5
hcf = math.gcd(x,y)


print(f"The computed GCD of {x} and {y} is {hcf}.")


Output

output

🤔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)}."


Output

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}.")


Output

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

🤔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}.")


Output

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 

You can also read about - Strong number in c

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

Let us brief out the article. Firstly, we saw different techniques to calculate the gcd of two numbers with their algorithm and code. That’s the end of the article. I hope you all like it.

If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder TraversalRegular and Bipartite graphsWhat Is Web2Py?Why To Use Web2py?Postbacks and Internationalization in web2pyThird Party Modules In Web2pyTasks In Web2py, and  XML in Web2py.

Recommended Readings:

Happy Coding!

Previous article
Fibonacci Series in Python
Next article
Python Program to Check Armstrong Number
Live masterclass