While reading Peter Shor's paper *Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer*, I came across the following quote:



> 
> "This scheme will thus work as long as $n$ is odd and not a prime power; finding factors of prime powers can be done efficiently with classical methods."
> 
> 
> 


I have two questions:


(1) How does one efficiently determine if a given number $N$ is a prime power, and


(2) How does one efficiently determine the factorization of a prime power? 


(Note: I have included these as separate questions since I am aware that many of the standard algorithms for determining a number is composite will not necessarily produce a proper factor.)



Algorithm for detecting prime powers
If N is a prime power it is of the form $p^i$ where $i \leq \log\_2(N)$. One can thus compute each of the first $\log\_2(N)$ roots of $N$, and test if the resulting number is (first an integer) and then if it is a prime using the [AKS algorithm](https://en.wikipedia.org/wiki/AKS_primality_test) (although perhaps Shor meant to use a randomized test, such as [Miller–Rabin](https://en.wikipedia.org/wiki/Miller-Rabin_primality_test), as the paper pre-dates AKS). Obviously if $N$ is a prime power this will produce the factorization.


