 # 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

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

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()

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:

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.