## Editorial for DMOPC '17 Contest 5 P3 - Mimi and Primes

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

For the first subtask, it is possible to iterate through all factors of a number in time, and then check if they are prime in time. If said factor is prime, we can iterate through the array and see if every number in the array is a multiple in time.

**Time Complexity:**

**Bonus:** The time complexity given above is a very loose upper bound. Can you establish a tighter bound?

For the second subtask, we can find the GCD of the array in , by using the Euclidean algorithm. We can then prime factorize the GCD in time, where is the GCD, and return the largest prime factor.

**Time Complexity:**

## Comments