View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
The Highest Common Factor [HCF], also called gcd, can be computed in python using a single function offered by math module and hence can make tasks easier in many situations.
Naive Methods to compute gcd
Way 1: Using Recursion
Python3
def hcfnaive[a, b]:
if[b == 0]:
return abs[a]
else:
return hcfnaive[b, a % b]
a =
60
b = 48
print["The gcd of 60 and 48 is : ", end=""]
print[hcfnaive[60, 48]]
Output
The gcd of 60 and 48 is : 12
Way 2: Using Loops
Python3
def computeGCD[x, y]:
if x > y:
small =
y
else:
small = x
for i in range[1, small + 1]:
if[[x % i == 0] and [y % i == 0]]:
gcd = i
return gcd
a = 60
b = 48
print
["The gcd of 60 and 48 is : ", end=""]
print [computeGCD[60,48]]
Output
The gcd of 60 and 48 is : 12
Way 3: Using Euclidean Algorithm
Python3
def computeGCD[x, y]:
while[y]:
x, y = y, x % y
return abs[x]
a = 60
b = 48
print ["The gcd of 60 and 48 is : ",end=""]
print [computeGCD[60, 48]]
Output:
The gcd of 60 and 48 is : 12
- Both numbers are 0, gcd is 0
- If only either number is Not a number, Type Error is raised.
❮ Math Methods
Example
Find the greatest common divisor of the two integers:
#Import math Library
import math
#find the the greatest common divisor of the two integers
print [math.gcd[3, 6]]
print [math.gcd[6, 12]]
print [math.gcd[12, 36]]
print [math.gcd[-12, -36]]
print [math.gcd[5, 12]]
print [math.gcd[10, 0]]
print
[math.gcd[0, 34]]
print [math.gcd[0, 0]]
Try it Yourself »
Definition and Usage
The math.gcd[] method returns the greatest common divisor of the two integers int1 and int2.
GCD is the largest common divisor that divides the numbers without a remainder.
GCD is also known as the highest common factor [HCF].
Tip: gcd[0,0] returns 0.
Syntax
Parameter Values
| int1 | Required. The first integer to find the GCD for |
| int2 | Required. The second integer to find the GCD for |
Technical Details
An int value, representing the greatest common divisor [GCD] for two integers
|
| 3.5 |
❮ Math Methods