If the problem required a more efficient solution then I would agree with Danil, but getting a brute force solution to this is not terribly difficult.

In the problem description it mentions that iterating up to n or n/2 will be too slow. If this is what you're doing, consider shortening the range on your loop (hint: the upper limit should be the largest factor of n, a value that involves fractional exponents).