Greatest common divisor (GCD) in Python
In this post, you will learn how to find the greatest common divisor (G.C.D) or highest common factor (H.C.F) of numbers using different methods in Python programming language.
Greatest common divisor (G.C.D) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers a, b, the greatest common divisor of a and b is denoted gcd(a,b). These are different ways to find the GCD or HCF using Python.
GCD in Python using math.gcd() Method
In Python, the math module contains various mathematical functions, which can be performed effortlessly utilizing the module. The math.gcd() method computes the greatest common divisor of two numbers.
Syntax of math.gcd()math.gcd(x, y)
Here, x and y are non-negative integers for computing GCD. It returns a positive integer value representing the greatest common divisor (GCD) for two integers.
Python gcd Exampleimport math
# Greatest common divisor of the two integers
print("GCD of (5, 2) = ",math.gcd(5, 2))
print("GCD of (4, 10) = ",math.gcd(4, 10))
print("GCD of (10, 0) = ",math.gcd(10, 0))
print("GCD of (-9, -16) = ",math.gcd(-9, -16))
print("GCD of (4, 14) = ",math.gcd(4, 14))
print("GCD of (6, 3) = ",math.gcd(6, 3))
Output of the above code-
GCD of (5, 2) = 1
GCD of (4, 10) = 2
GCD of (10, 0) = 10
GCD of (-9, -16) = 1
GCD of (4, 14) = 2
GCD of (6, 3) = 3
GCD in Python using for loop
Here, we define a function to compute the H.C.F of two numbers and return it. In each iteration, we check if our number perfectly divides both the user input numbers. If this is true, we store the number as H.C.F. At the completion of the loop, we conclude with the largest number that perfectly divides both the numbers.
# Python program to find GCD of two numbers
# define a function
def get_gcd(a, b):
# pick the smaller number
if a > b:
smaller = int(b)
else:
smaller = int(a)
for i in range(1, smaller+1):
if((a % i == 0) and (b % i == 0)):
gcd = i
return gcd
x = input("Enter the first number: ")
y = input("Enter the second number: ")
print("The G.C.D. is ", get_gcd(int(x), int(y)))
Output of the above code-Enter the first number: 39
Enter the second number: 2
The G.C.D. is 1
Enter the first number: 48
Enter the second number: 34
The G.C.D. is 2
GCD in Python using while loop
In the given Python program, we have used the while loop to compute the GCD of two numbers.
x = int(input('Please input the first integer:'))
y = int(input('Please input the second integer:'))
while y != 0:
gcd = y
y = x % y
x = gcd
print("The G.C.D. is ",gcd)
Output of the above code:
Please input the first integer:6
Please input the second integer:10
The G.C.D. is 2
GCD in Python using Recursion
Recursion function is a function which is calling itself. The following code finds the greatest common divisor of user inputs using the recursion function. A recursion function continues until some condition is met to prevent it. That's why we use the if statement to break the infinite recursion.
def compute_gcd(a, b):
if(b == 0):
return a
else:
return compute_gcd(b, a % b)
x = input("Enter the first number: ")
y = input("Enter the second number: ")
print("The G.C.D. is ", compute_gcd(int(x), int(y)))
Output of the above code-GCD in Python using Euclidean algorithm
The Euclidean algorithm is an efficient way to find the greatest common divisor of two numbers, the largest number that divides them both without a remainder.
Example# Function to find GCD the Using Euclidian algorithm
def compute_gcd(a, b):
while(b):
a, b = b, a % b
return a
x = input("Enter the first number: ")
y = input("Enter the second number: ")
print("The G.C.D. is ", compute_gcd(int(x), int(y)))
Output of the above code-
Enter the first number: 78
Enter the second number: 40
The G.C.D. is 2
Enter the first number: 30
Enter the second number: 15
The G.C.D. is 15
Related Articles
Python program to multiply two numbers
Insert XML Data to MySQL Table using Python
Remove last element from list Python
Multiply all elements in list Python
ASCII value in Python
Python String isalpha() Method
Python YouTube Downloader with Pytube
Python alphabetical order
Pandas Converting Strings to datetime
Pandas fillna multiple columns
Stemming and Lemmatization in Python
Python | Generate QR Code using pyqrcode module
Extract text from image Python
How to Send Text Messages With PHP
Fibonacci Series In Python | Python Program To Print
File Handling in Python
How to convert XML to JSON in Python
Python XML to Dictionary
Serialize Python dictionary to XML