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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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**

1 2 3 4 5 6 7 8 9 10 11 |
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()**

1 2 3 4 5 6 7 |
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:**

1 2 3 4 5 6 7 8 9 10 11 12 13 |
#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.