What is fastest algorithm for factoring out square from number
Using state of the art factoring algorithms, you can substantially improve on the algorithm you state. It appears that no algorithm better than factoring is known at the moment. See this question on mathoverflow.