Estimate how many times faster it will be to find gcd (31415, 14142) by Euclid's algorithm compared with the algorithm based on checking consecutive integers from min{m, n} down to gcd (m, n).

Euclid's algorithm is at least 14142 / 10 = 1400 times faster than the Consecutive integer checking method.

On the other hand, Euclid's algorithm is at most 28284 / 10 = 2800 times faster than the Consecutive integer checking method.

Explanation:

Formula for calculating GCD (Greatest Common Divisor) is

gcd (m, n) = gcd (n, m mod n)

Calculating the GCD by applying the Euclid's algorithm:

gcd (31415, 14142) = gcd (14142, 3131)

gcd (3131, 1618)

gcd (1618, 1513)

gcd (1513, 105)

gcd (105, 43)

gcd (43, 19)

gcd (19, 5)

gcd (5, 4)

gcd (4, 1)

gcd (1, 0) = 1

If we count the above steps, then the number of divisions using Euclid's algorithm = 10

While the Consecutive integer checking will take 14142 iterations but will take 14142 * 2 = 28284 divisions.

Euclid's algorithm is at least 14142 / 10 = 1400 times faster than the Consecutive integer checking method.

On the other hand, Euclid's algorithm is at most 28284 / 10 = 2800 times faster than the Consecutive integer checking method.