Given n numbers, you have to make all the numbers equal to one in minimum number of moves. Only operation allowed is to take a subset of numbers and divide all of them by a prime p if their gcd is divisible by p.
Let us first solve the problem when all the numbers are of the form p ei where p is a prime number.
Note that in this case, you will try to divide the selected number by p.
What is the lower bound on minimum number of moves which will be required ?
Lower Bound on minimum number of moves required will be max(ei) for all i.
Can you prove that the above lower bound is the optimal solution ?
Yes, this is a greedy strategy in which we take all numbers in subset which are divisible by p.
Can you extend this algorithm for the original problem ?
Yes, find the sum of the maximum degree of all prime numbers in the factorisation of all numbers.
Proof is very easy and left as an exercise for the reader.
#factorisation of a number
As all numbers are less than 106, we can find all prime numbers less than 103 using sieve or simple brute force.
Then for factorising any number we will iterate over all prime factors which are less than square root of the number because there can’t be 2 factors which are greater than square root of the number.
We just have to check for primes 2 and 3 only as each number is less than or equal to 3.
O(N) factorisation will pass.
You can use one of the methods explained in the previous section.
Some Interesting Reads
Setter and Tester Solutions: