Ever heard of the Euclidean algorithm??

From wikipedia:

In mathematics, the Euclidean algorithm[a] (also called Euclid’s algorithm) is an efficient method for computing the greatest common divisor (GCD) of two integers, also known as the greatest common factor (GCF) or highest common factor (HCF).

I have just written a short python program for finding the GCD.. Enjoy..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Efficient method for computing the greatest common divisor # X and Y is the two numbers x=42 y=24 def findGCD(a,b): print a,b if b==0: print "Answer is " + str(a) return a return findGCD(b,a%b) findGCD(x,y) |