Python Implementation of the Euclidean Algorithm
Posted: Sat Jan 02, 2016 10:20 am
This is the python implementation of the Euclidean Algorithm. The algorithm finds the greatest common divisor (gcd) of any two integers. A simple Python code below is an abstraction of the flow chart below, which is the Euclid's Algorithm for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B.
(This image is take from here.)
To run the code, go to the terminal and type what you see after $ and replace name_of_the_code appropriately
Then you will be taken to an interactive python interpreter
Try
to have
(This image is take from here.)
- """This is a python code to solve for the gcd of two integers"""
- def gcd (a,b):
- while (b!=0):
- r = a%b
- a = b
- b = r
- return a
Code: Select all
tssfl@U90-U100:~$ python -i name_of_the_code.py
Code: Select all
>>>
Code: Select all
>>> gcd (2171, 2613)
Code: Select all
13