Have you ever wondered how to find the GCD of two numbers? This article will show you how to write a Python program to find the GCD of two numbers. The Greatest common divisor of two numbers is the largest number that divides both of those numbers without leaving a remainder. In Python, this function is denoted by GCD().
GCD stands for Greatest Common Divisor and is also known as HCF (Highest Common Factor). Python has a built-in function that can help. This handy tool can often be helpful in statistics and mathematics. So whether you’re a student looking for an activity to do during your break, or a professional trying to solve a complex problem, get started with our tutorial and learn Python Program to find the GCD of two numbers in no time in Python.
Table of Contents
What is GCD?
GCD is a mathematical formula that calculates the greatest common factor, which can divide two numbers perfectly. For example, the GCD/HCF of two numbers, 12 and 18, is 6. Since 6 is GCD, that completely divides 12 and 18 both.
How to find GCD of Two Numbers in Python?
1. Using GCD Function
Python has the inbuilt math.gcd () function that can be used after importing the math module. So let’s look at an example to understand better.
import math
a = 32
b = 128
print(" GCD of a and b is ", math.gcd(a, b))
print(" GCD of 18 and 24 is ", math.gcd(18, 24))
print(" GCD of 0 and 0 is ", math.gcd(0, 0))
print(" GCD of two number -48 and -12 is ", math.gcd(-48, -12))
Output
2. Using Recursion
Recursion is a function that will be called continuously and repeat itself until the specified condition is met. This way, it returns the GCD of two numbers. Check out the following example to understand working.
def gcd(a, b):
if(b == 0):
return a
else:
return gcd(b, a % b)
a =int (input ("Enter a: "))
b =int (input ("Enter b: "))
result = gcd(a, b)
print("GCD of a & b : ", result) Output
3. Using Loop
GCD of two numbers can be found using Python Loops. Here is an example code snippet.
def loop_gcd(x, y):
if x > y:
temp = y
else:
temp = x
for i in range(1, temp + 1):
if (( x % i == 0) and (y % i == 0 )):
GCD = i
return GCD
a = int(input (" Enter a: ") )
b = int (input (" Enter b: "))
result = loop_gcd(a, b)
print("GCD of two number is: ",result)
Output
4. Using Euclidian Algorithm
In Euclid’s algorithm, the greater number is divided by a smaller number, and then the remainder is taken. Afterward, the smaller number is divided by the remainder produced previously. This process is repeated until we get the 0 in the remainder. This algorithm follows the process of finding HCF in mathematics.
Now let’s look at the example code snippet to understand the working of the Euclidian Algorithm.
def gcd(x, y):
if (x == 0):
return y
if (y == 0):
return x
if (x == y):
return x
if (x > y):
return gcd(x-y, y)
return gcd(x, y-x)
x = int(input (" Enter x: "))
y = int(input (" Enter y: "))
if(gcd(x, y)):
print('GCD of', x, 'and', y, 'is', gcd(x, y))
else:
print('NOT FOUND')
Output
FAQs
Is there a more straightforward way to find the GCD of two numbers other than writing code?
There may not be a simpler way to find the GCD of two numbers other than writing code, but many tools can help you do this quickly and easily. Popular options include Google Sheets and Excel. In Google Sheets, you can use the “GCD” function to solve equations very quickly. Similarly, in Excel, you can use the “MOD” function, which will return the remainder after the division of two Numbers.
How would you deal with a number that is too large or small to be processed by the Python GCD function?
In Python, if you encounter a number that is too large or small to be processed by the GCD function, there are several ways to approach it. You can use the max() and min() functions for too big numbers. For numbers that are too small, you can use floor(), ceil(), round(), or truncate().
What is the difference between Python and other programming languages?
One of the most notable differences between Python and other languages is how data is represented. For example, in Python, information is typically stored in objects rather than individual variables. This makes coding much simpler because you don’t have to worry about memory space or how an operation will affect your overall code flow.
See Also:
Python program to find area of traingle
Conclusion
Thanks for reading. This article showed you how to find the GCD of two numbers using Python. Learning this skill can be very useful, especially if you need to solve math puzzles or crunch numbers for work. I hope this was helpful.
