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