File tree Expand file tree Collapse file tree 1 file changed +24
-0
lines changed Expand file tree Collapse file tree 1 file changed +24
-0
lines changed Original file line number Diff line number Diff line change
1
+ """
2
+ Greatest common divisor(GCD) of two integers X and Y is the largest integer that divides both X and Y.
3
+
4
+ References :
5
+ https://en.wikipedia.org/wiki/Euclidean_algorithm
6
+ https://proofwiki.org/wiki/Euclidean_Algorithm
7
+ http://stackoverflow.com/questions/6005582/how-does-the-euclidean-algorithm-work
8
+
9
+
10
+ Algorithm :
11
+ * If X = 0 then GCD(X,Y) = Y, as GCD(0,Y) = Y.
12
+ * If Y = 0 then GCD(X,Y) = X, as GCD(X,0) = X.
13
+ * Write X in quotient remainder form (X = Y * Q + R).
14
+ * Find GCD(Y,R) using the Euclidean algorithm since GCD(X,Y) = GCD(Y,R).
15
+ """
16
+
17
+ def greatest_common_divisor (x ,y ):
18
+ if (y == 0 ):
19
+ return x
20
+ else :
21
+ return greatest_common_divisor (y ,x % y )
22
+
23
+ if __name__ == "__main__" :
24
+ print (greatest_common_divisor (20 ,25 ))
You can’t perform that action at this time.
0 commit comments