Euclidean Algorithm to find GCD

By Arijit Roychaudhury

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:

• Python Program to find LCM of two numbers