Create GCD.py

vedangmehta · vedangmehta · commit ae253fe651d6 · 2015-08-11T18:07:21.000+05:30
Euclidean algorithm to find the GCD of two numbers.
diff --git a/misc/GCD.py b/misc/GCD.py
@@ -0,0 +1,24 @@
+"""
+Greatest common divisor(GCD) of two integers X and Y is the largest integer that divides both X and Y.
+
+References : 
+https://en.wikipedia.org/wiki/Euclidean_algorithm
+https://proofwiki.org/wiki/Euclidean_Algorithm
+http://stackoverflow.com/questions/6005582/how-does-the-euclidean-algorithm-work
+
+
+Algorithm :
+* If X = 0 then GCD(X,Y) = Y, as GCD(0,Y) = Y.
+* If Y = 0 then GCD(X,Y) = X, as GCD(X,0) = X.
+* Write X in quotient remainder form (X = Y * Q + R).
+* Find GCD(Y,R) using the Euclidean algorithm since GCD(X,Y) = GCD(Y,R).
+"""
+
+def greatest_common_divisor(x,y):
+    if(y == 0):
+        return x
+    else:
+        return greatest_common_divisor(y,x%y)
+
+if __name__ == "__main__":
+    print(greatest_common_divisor(20,25))
