1a. find gcd (31415, 14142) by applying euclid's algorithm 1b. estimate how faster it is compared with consecutive integer checking 2. what does the euclid's algorithm do if the first number is smaller than the second one? what is the largest number of times it can happen in one execution of the algorithm? 3a. what is the smallest number of divisions made by euclid's algorithm among all inputs between 1 and 20? 3b. what is the largest number of divisions made by euclid's algorithm among all inputs between 1 and 20?

Question

Malachi

Mathematics

20 June, 05:15

1a. find gcd (31415, 14142) by applying euclid's algorithm 1b. estimate how faster it is compared with consecutive integer checking 2. what does the euclid's algorithm do if the first number is smaller than the second one? what is the largest number of times it can happen in one execution of the algorithm? 3a. what is the smallest number of divisions made by euclid's algorithm among all inputs between 1 and 20? 3b. what is the largest number of divisions made by euclid's algorithm among all inputs between 1 and 20?

+3

Answers (1)

Know the Answer?

Destiny Scott · Answer 1

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