euclid.py

euclid.py

#!/bin/env python2

import sys

# get first number
a = input('Enter first number: ')
print('a = %d' % a)

# get second number
b = input('Enter second numner: ')
print('b = %d' % b)

# a = b?
if a == b:
    print('a = b, so GCD(%d,%d) = %d' % (a,b,a))
    sys.exit()

# a > b?
# if not, swap
if a < b:
    tmp = a
    a = b
    b = tmp
    print('a < b, so swap a and b: a = %d, b = %d' % (a,b))

print('')

# r_{k-2}
rk2 = a

# r_{k-1}
rk1 = b

# r_k
rk = b

# a    =    b q  + r
# rk-2 = rk-1 qk + rk

k = 0
while rk1 > 0:
    rk = rk2 % rk1
    print('%d:\tr_k-2 = %d\tr_k-1 = %d\trk = %d' % (k, rk2, rk1, rk))
    rk2 = rk1
    rk1 = rk
    k += 1

print('%d:\tr_k-2 = %d\tr_k-1 = 0' % (k, rk2))

# rk2 is the last nonzero rk-1
print('\nGDD(%d, %d) = r_k-2 = %d' % (a,b,rk2))

You may need to chmod +x euclid.py before running