Answer:
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.
