What's the quickest way to check if an integer is a perfect power? I want to write a program that checks whether a consumed positive integer, n, is a perfect power or not. What would be the most efficient implementation of that program? I can think of an obvious implementation (checking if all 0 < i <= n/2 are power roots of n), but I'm rusty on number theory so I'm not sure if there exists a better way. I wouldn't want to get into case analysis, but if the gains in efficiency are significant, I'd consider it.