How does one find out whether $N = a^b$ for some $b$?
Yes, your approach is a good one.  The only thing you missed is that there's a simple upper bound $b \le \lg N$.

Do you see why?  It's easier to see why if you state more carefully the problem  you are trying to solve.  You are asking whether there exist $a,b \in \mathbb{N}$ such that $a \ge 2$, $b \ge 2$, and $a^b=N$.  Taking logs of both sides, we get $b \lg a = \lg N$.  From the fact that $a \ge 2$, we see $\lg a \ge 1$, so $b = (\lg N)/(\lg a) \le \lg N$.

Therefore, here is a simple algorithm:


For $b=2,3,\dots,\lg N$:


Use binary search to search for $a \in \mathbb{N}$ such that $a^b=N$.



Each iteration of the loop will take $O(\lg N)$ time (the time for a binary search over at most $N$ possibilities), and you do $\lg N$ iterations of the loop, so the total running time $O((\lg N)^2)$.

In particular, yes, this will always terminate.  You don't need to keep trying new values for $b$ forever, since we know that $b$ is an integer and is no larger than $\lg N$.

The running time of the algorithm can be improved a bit by replacing the binary search with a faster algorithm to compute $\sqrt[b]{N}$; for instance, you could use Newton's method.  But the basic method above is already very efficient.



You might be tempted to iterate over all possible values of $a$, and then do a binary search for $b$.  Don't do that; there are $\Theta(\sqrt{N})$ possible values of $a$, so this will be unavoidably slow.

Instead, a better approach is to iterate over all possible values of $b$, and then do a binary search for a matching $a$.  This is much faster, as it needs only $\Theta(\lg N)$ binary searches rather than $\Theta(\sqrt{N})$ of them.

One person mentioned factoring $N$.  This is much slower.  Our best algorithms for factoring run in subexponential time; they are much slower than the $\Theta((\lg N)^2)$ running time of the algorithm above.