Python GCD – 4 Ways to Find GCD or HCF

Here I will show you 4 different ways to find GCD in Python using program examples.

GCD also known as HCF (Highest Common Factor). So let’s see how we’ll do it.

Method 1: Using Loop

```n1 = 48
n2 = 36

#find smaller
if(n1>n2):
smaller = n2
else:
smaller = n1

#getting hcf
i = 1
while(i<=smaller):
if(n1%i==0 and n2%i ==0):
hcf = i
i  = i+1

print("hcf = ", hcf)```

Output:

hcf = 12

So in this program, first we assign values to n1 and n2, then we’ll find smaller number from both of the numbers.  After that we’ll start loop from 1 to smaller number to find a number which can be fully divisible with both of the numbers n1 and n2 and store into a new variable named as hcf. At the end of the loop we’ll get the highest number stored in hcf variable which can fully divide both of the numbers n1 and n2. That highest number will be our hcf.

Method 2: Using Recursion

```def find_hcf(n1,n2):
if(n2==0):
return n1
else:
return find_hcf(n2,n1%n2)

n1 = 48
n2 = 36

hcf = find_hcf(n1,n2)
print ("highest common factor = ", hcf)```

Output:

highest  common factor = 12

So here we have a recursive function which receive two arguments and return the Highest common factor between them.

Method 3: Using math.gcd()

```import math

n1 = 48
n2 = 36

hcf = math.gcd(n1,n2)
print("Highest Common Factor = ", hcf)```

Output:

Highest Common Factor = 12

Python has an inbuilt method to find out the GCD. We even doesn’t need to think how to code to find GCD. All we have to do is just use math.gcd() method and it will return the GCD.

Method 4: Using Euclidean Algorithm

Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers. Here is the pseudocode to show how we can find GCD using Euclidean Algorithm.

Pseudocode:

function gcd(a, b)

while b ≠ 0

t := b;

b := a mod b;

a := t;

return a;

Program:

```#implementing Euclidean algo
def get_gcd	(x, y):

while(y):
x, y = y, x % y

return x

n1 = 48
n2 = 36

hcf = get_gcd(n1,n2)
print("Highest Common Factor = ", hcf)```

Output:

Highest Common Factor = 12

In this program, get_gcd(int, int) function is used to implement the Euclidean algorithm. For more details on Euclidean algo please visit https://en.wikipedia.org/wiki/Euclidean_algorithm

If you’ve any problem or suggestion related to python gcd programs then comment down below.

1 thought on “Python GCD – 4 Ways to Find GCD or HCF”

1. I like all that you showed in the tutorial on the 4 ways to find the HCF or,as you say,also called the GCD.
you guys in this data programming field are really in the cloud.I can google “what is GDC” and get what it means.Since you say that it’s a tutorial,then you’re in my sphere-Education.When I teach maths to my students I simply use factors to find the highest common factor.
Thus,the HCF of 48 and 36 :

48=1×48;2×24;3×16;4×12;6×8 36=1×36:2×18:3×12:4×9:6×6
Factors of 48:1,2,3,4,6,8,12,16,48 Factors of 36:1,2,3,4,6,9,12,18,3612
The highest common factor of both integers is- 12.