DEV Community is a community of 639,856 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Euclidean Algorithm meaning & python snippet

This algorithm helps us get the greatest common divisor(gcd) of 2 integers. In other words, the result of our computation is the highest possible number `(lets say 1)` that we can divide by two given numbers `(4 and 5)` which will give a remainder `(or you could say left over after a division)` of zero for both given numbers. Lets break this down a little bit :
our two numbers earlier were `4` and `5`, but these could be any random numbers which follow two rules :
1st >> one number must be larger than the other.
2nd >> both must not be even numbers.
The euclidian algorithm formula is `q = a * b + r` where the letters are placeholders for numbers forexample

``````5 = 4 * 1 + 1 or
11 = 2 * 5 + 1
``````

Lets get our hands a little dirty and see how we arrived to the answers of 5 and 11 above:
`now is the time to open your editor and create a python file so we can write some simple code. my file is called index.py`
When calculating we always have our 2 numbers, remember earlier we chose `(4 and 5)`. These numbers replace `q` and `a` whereby `q` takes the bigger number `(5)` and `a` the smaller `(4)` so `5 = 4 * b + r` therefore in `index.py`

``````# formula is q = a * b + r
q = 5
a = 4
``````

our task is to find numbers to replace `b` and `r` to complete our equation. according to the Euclidian theorem, `b` is the number of times `a` goes into (divides) `q` while `r` is the remainder of that operation.
so `5` goes into `4` once with a remainder of `1` so we will equate our remainder to `r` and our initial answer to b. In python we could use an inbuilt function called `divmod( )` to do this computation and it takes the two numbers as arguments and returns a quotient and remainder as the result in an array therefore in `index.py`

``````# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
``````

However according to the Euclidian theorem, our remainder must be zero so if `r` isn't `0` we aren't done. It states that we have to place `a` in the position of `q` and `r` in the position of `a` or simply replace our initial values that were used in the calculation by new values following the above procedure therefore in `index.py`

``````# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
q = a
a = r
``````

Take a scenario where you didn't use `(4 and 5)` , probably (11 and 5). You will have to repeat the calculations until `r = 0`. When `r = 0` , we obtain the gcd from the value of r just exactly before you did the last calculation to obtain `r = 0` for us to get the desired final result therefore in `index.py` we can use a for loop to do our calculations over and over until `r = 0` :

``````# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
q = a
a = r
finalResult = 0 #initialize a variable outside the for loop so
#that it is accessed globally
for i in range(q):
finalResult = r #store our gcd value as the loop is starting so
#that we can capture the previous value of r
#before the calculation which equates `r = 0`
result = divmod(q,a)
b = result[0]
r = result[1]
if r == 0:
break #constantly check the current value in r and make sure
#when it is 0 you can stop the loop
q = a
a = r
print(finalresult)
``````

And that's it folks, Enjoy