In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of October 25th
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #03 exercise sheet]

In this problem you should submit a function as described. Inside the function do not print anything that was not asked!

The name of the .py source file you submit to Mooshak should NOT start with a digit (you will get an error if you submit it like that).

[IP032] The Prime Suspects

Every integer has its secrets, but some can’t hide them for long. Your task is to interrogate a number and reveal its full list of prime suspects: the prime factors that, when multiplied together, reconstruct the original number.

For example:

• 84 should confess as being equal to 2*2*3*7
• 29 stays stubborn as 29 (a prime that works alone)

The Problem

Write a function factorize(n) that takes an integer n and returns a string representing its prime factorization in the form n=p₁*p₂*...*p_k, with p_i being its prime factors in increasing order.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

NOTE: the limits on n are high and you must have an efficient solution that can compute this quicker than simply trying to divide n by all possible integers from 1 to n (or you risk having Time Limit Exceeded). Your program will need to be able to compute around 100 factorizations in less than one second.

print(factorize(84))
print(factorize(29))
print(factorize(6))
print(factorize(630))
print(factorize(100))
print(factorize(13))

84=2*2*3*7
29=29
6=2*3
630=2*3*3*5*7
100=2*2*5*5
13=13