Write a python program that defines three functions to find gcd of two integers (the first one using Euclids algorithm, 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.

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: used (25, 15)

5

5

5

Time for gcd1 is 0.00076920200000002

Time for gcd2 is 2.8516841790000003

Time for gcd3 is 1.5120790379999995