I'm writing a program that does symbolic algebraic computation. The desired behavior for taking the $n$th root of an integer $r$ is to return $p\sqrt[n]{\frac{r}{p^n}}$, where $p$ is the largest integer such that $p^n$ divides $r$. In other words, the program moves any factors $r$ might have that are perfect $n$th powers outside the surd.
I have been using a naive method of trial division to find these factors, but this approach is now too inefficient for my purposes. Is the problem of finding perfect $n$th power factors any easier in the computational complexity sense than factoring an integer completely? - are there any additional tricks that can be brought to bear on this less general problem?