Question

Find the largest number of divisions made by Euclid’s algorithm for computing gcd(m, n) for 1≤ n ≤ m ≤ 100.

Answer 1

Answer: 

#Largest number of divisions was: 11 for m:55 and n:89

Using the below program we find that for numbers 55 and 89 the largest number of division was maximum and it is 11

======================================================================

count = 0
def gcd(a, b):
    global count
    count += 1
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)


def main():
    global count
    largest_divisions = count
    num_m = num_n = 0
    for m in range(1, 101):
        for n in range(1, 101):
            gcd(m, n)
            if largest_divisions < count:
                largest_divisions = count
                num_m = m
                num_n = n
            count = 0
    print('Largest number of divisions was: {} for m:{} and n:{}'.format(largest_divisions,num_m,num_n))

main()