please use python to solve, only answer the (a) part

Problem 4 (a) Write a function alt_gcd(a,b) that returns the god of a, b (where a, b are positive integers), but do NOT use the Euclidean algorithm. Rather, use the factoring function you wrote for last homework (or some modification of it); recall that if we know the prime factorizations of both a, b, we can find the gcd by looking at the smaller power of each prime that occurs in each of a, b. (b) Let f(n) be the maximum of the running time of your alt_gcd(a,b) function, where a, b range over all pairs of n digit numbers. Using timed experiments, guess the rough order of growth of f(n) as n 00 (i.e. is it logarithmitic, linear, quadratic, exponential)? The time and %time commands may be useful for doing the timing. (I am not actually asking you to compute f, just to guess it's order of growth. The maximum run-time for an n-digit number is not so different than the run-time for a random n digit number, so you don't have to try all n digit numbers, just a few random ones.)