• Active Topics 

Python Implementation of the Euclidean Algorithm

Including Cython, Jython, IronPython, PyPy, Django framework, and interpreters: Ipython, IPython Jupyter/Notebook, CPython


Post Reply
User avatar
Eli
Senior Expert Member
Reactions: 183
Posts: 5212
Joined: 9 years ago
Location: Tanzania
Has thanked: 75 times
Been thanked: 88 times
Contact:

#1

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.

Image

(This image is take from here.)

  1. """This is a python code to solve for the gcd of two integers"""
  2. def gcd (a,b):
  3.     while (b!=0):
  4.         r = a%b
  5.         a = b
  6.         b = r
  7.     return a

To run the code, go to the terminal and type what you see after $ and replace name_of_the_code appropriately

Code: Select all

tssfl@U90-U100:~$ python -i name_of_the_code.py
Then you will be taken to an interactive python interpreter

Code: Select all

>>>
Try

Code: Select all

>>> gcd (2171, 2613)
to have

Code: Select all

 13
0
TSSFL -- A Creative Journey Towards Infinite Possibilities!
User avatar
Eli
Senior Expert Member
Reactions: 183
Posts: 5212
Joined: 9 years ago
Location: Tanzania
Has thanked: 75 times
Been thanked: 88 times
Contact:

#2

You can now run this on this forum, copy, go here and paste to test it:

  1. """This is a python code to solve for the gcd of two integers"""
  2. def gcd (a,b):
  3.     while (b!=0):
  4.         r = a%b
  5.         a = b
  6.         b = r
  7.     return a
  8.  
  9. gcd = gcd (2171, 2613)
  10. print(gcd)

0
TSSFL -- A Creative Journey Towards Infinite Possibilities!
User avatar
Eli
Senior Expert Member
Reactions: 183
Posts: 5212
Joined: 9 years ago
Location: Tanzania
Has thanked: 75 times
Been thanked: 88 times
Contact:

#3

TSSFL -- A Creative Journey Towards Infinite Possibilities!
Post Reply
  • Similar Topics
    Replies
    Views
    Last post

Return to “Python Programming”

  • Information
  • Who is online

    Users browsing this forum: No registered users and 1 guest