Problem Statement We used Euclids algorithm to find the greatest common divisor (gcd) of two given integers in class. Come up with two other algorithms to find the gcd of two integers. Write a program that defines three functions to find gcd of two integers as described above (the first one using Euclids algorithm as we did in class, the other two use your own algorithms), you can name the functions gcd1, gcd2, and gcd3. All three functions take two integers as parameters and return the gcd of them. Use two integers to test the functions above. Now use timeit module in Python to measure and print out the time taken by the three functions, respectively. Use random.randint to generate two random integers between 1 and 100000, and the number used for timeit should be 1000 times. Check sample output below. Name your program gcdAlgorithms_yourLastName.py You need to include some import statements at the beginning of your program such as: import timeit import random The following is how to time the algorithm gcd1 with two random numbers: t1 = timeit.Timer(gcd1(num1, num2), from __main__ import gcd1, num1, num2) Sample Output: (I used (25, 15) to test the gcd functions)

5

5

5

Time for gcd1 is 0.00076920200000002

Time for gcd2 is 2.8516841790000003

Time for gcd3 is 1.5120790379999995