# Need help in NDIVPHI-Spoj

Problem Statement is here. I searched for the editorials. But did not get a good one. It was recommended by many people in Quora. Can anyone please help in this question?

First of all you should be able to come up with a formula for phi(m) in terms of m and its prime factors. This can be easily searched online (here) or derived using inclusion exclusion formula. Now, in the formula you can notice that m occurs, which in the problem NDIVPHI simply cancels with the numerator. Now the remaining terms are simply the distinct prime factors of m arranged in some manner. Since, the question asks for finding the smallest possible value of integer, there is no point in having the same prime again as a divisor of m. So we take distinct prime factors only. Finally we want to maximise the value of the function so we simply go on taking primes till the number formed is less than m.

Here is a final implementation in python, (easy to handle large numbers) of the above described process.