# Euclidean Algorithm to find GCD

GCD is the greatest common divisor of two numbers. Ex: the gcd of 2 and 4 would be 2. In this tutorial, we will be learning how to find GCD using Euclidean Algorithm in Python.

**Euclidean Algorithm :**

Using this algorithm if we want to find the gcd value of A and B then the form would be something like this :

A= B*q +r

Where q= A/B and r=A%B. We have to repeat this algorithm in such a way that the final remainder(r) would be 0. One thing to keep in mind that in each step, A value would be replaced by B and B value would be replaced by r.

So , let us take a small example to understand this well…

We want to compute gcd(8,12). Here our A=12 and B=8.

12=8 * (12/8) +(12%8) = 8 * 1+ 4

8=4*(8/4) + (8%4) = 4 * 2 + 0

So, here we got 0 in remainder, so we have to stop and in that sequence, the B value would be the result. So, here our B value is 4. So, the resultant GCD will be 4.

## Find the GCD using Euclidean Algorithm in Python

Here is the code of the above algorithm in Python :

#Euclidean Algo to Find GCD def gcd(a,b): if(a==0): return b // THE FINAL RESULT WOULD BE PRODUCED FROM HERE else : return gcd(b%a,a) // RECURSION TO CALL EACH STEPS

a=20 #input 1 b=24 #input 2 print(gcd(a,b)) #Output : 4

The complexity of the above algorithm will be O(log(min(a,b)))

Also read:

## Leave a Reply