GCD Of Two Numbers

Naive Algorithm

Function NaiveGCD(a, b)

best <- 0
for d from 1 to a+b:
    if d|a and d|b:
        best <- d
return best

  • Runtime approximately a+b
  • Very slow for 20 digit numbers

Python Implementation

def gcd(m, n):
    gc = 0
    for i in range(1, m+n):
        if m % i == 0 and n % i == 0:
            gc = i
    return gc

default_a = 3918848
default_b = 1653264

a = input("Enter a: [%s]" % default_a)
b = input("Enter b: [%s]" % default_b)

a = a or default_a
b = b or default_b

g = gcd(int(a), int(b))

print("GCD is: ", g)

Continue reading GCD Of Two Numbers