I believe you have the right idea, but I'm not so sure about one thing in specific, which shows up multiple times in your solution. While for powers of two, I believe you are correct because each power only has one instance in which it occurs, this is not necessarily true for powers of the other divisors.
For example, you can have [unparseable or potentially dangerous latex formula] show up in [unparseable or potentially dangerous latex formula] and in [unparseable or potentially dangerous latex formula].
So I then claim that the values returned by checking for powers of 3 and 5 will just be much larger than those for 2 and 67.
For 67, you will end up having a value of 67 for the evaluation of pow(n) 77 times, because the largest multiple of 67 less than 5300 is 79; 79, 71, and 73 are all primes larger than 67, and 67^2 comes up once (79-3+1)=77.
So the largest power should be 77 I think.
You know I'm not even sure anymore...I get distracted from my scores by chocolate =(