Skip to content

Commit ae253fe

Browse files
committed
Create GCD.py
Euclidean algorithm to find the GCD of two numbers.
1 parent 91cae9b commit ae253fe

File tree

1 file changed

+24
-0
lines changed

1 file changed

+24
-0
lines changed

misc/GCD.py

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
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))

0 commit comments

Comments
 (0)