Finding the greatest common divisor (GCD) of two numbers is a very useful calculation in many fields, such as mathematics, engineering, and computing. It is often necessary to find the GCD of two numbers to solve a particular problem.
In Python, there are two main ways to calculate the GCD, ie, the GCD of two numbers using an in-built function which is math.gcd() function or by writing your own recursive function.
Python Program to Find GCD of Two Numbers Using in-build Function
The math.gcd() function is an in-built Python function that takes two integers as parameters and returns the GCD of the two numbers. This is the simplest and most efficient way to calculate the GCD.
To use the math.gcd() function, we must first import the math module. Then, we can assign two numbers to variables, a and b. Finally, we can call the math.gcd() function with a and b as parameters and it will return the GCD of the two numbers.
Alternatively, we can write our own recursive function to calculate the GCD of two numbers. This is useful if we want to understand exactly how the GCD calculation works. The code for a recursive GCD function is given below.
This code takes the two numbers as input and stores them in variables a and b. Then, the gcd() function is defined which takes a and b as parameters. The function checks if the second number is equal to 0 and if it is, it returns the first number as the GCD.
If it is not equal to 0, then the function calls itself, swapping the parameters and passing b as the first parameter and a modulo b as the second parameter. Doing this ensures that the function will eventually reach the base case of b being equal to 0, at which point it will return a as the GCD of the two numbers. Finally, the program calls gcd() with a and b as parameters and prints the GCD. Example:
#GCD of Two Numbers in Python Using in-build Function
import math
# we are taking a number from user as input
# entered value will be converted to int from string
a=int(input("Enter first number:"))
b=int(input("Enter second number:"))
print("The GCD of",a ,"and", b ,"is",math.gcd(a, b))
Output:
Enter first number:24
Enter second number:15
The GCD of 24 and 15 is 3The program begins by asking the user to enter two numbers, which are then stored in variables a and b. Then, the math.gcd() function is called with a and b as parameters and the GCD of the two numbers is returned. Finally, the program prints out the statement “The GCD of and is “, in this case, “The GCD of 24 and 15 is 3”. This output indicates that the GCD of 24 and 15 is 3.
In conclusion, it is possible to calculate the GCD of two numbers in Python using in-build function which is math.gcd() function or a recursive function. The math.gcd() function is the most efficient way to calculate the GCD while writing a recursive function is useful to understand how the GCD calculation works.
For More Python Programming Exercises and Solutions check out our Python Exercises and Solutions