Skip to content

Instantly share code, notes, and snippets.

Created March 30, 2016 07:30
What would you like to do?
GCD computing without modulo neither division ops
# computes the greatest common divisor
# with a small subset of math operations
# that does not include `division` or `modulo`
def gcd(a, b):
while b>0:
c = a
a = b
while(c >= b):
c -= b
b = c
return a
if __name__ == '__main__':
from fractions import gcd as gcd_
for i in xrange(20):
print gcd(13, i), gcd_(13, i)
print gcd(20, i), _(20, i)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment