A positive integer N is a power if it is of the form qk , where q, k are positive integers and k > 1.

(a) Give an efficient algorithm that takes as input a number N and determines whether it is a square, that is, whether it can be written as q2 for some positive integer q. What is the running time of your algorithm?

(b) Show that if N = qk (with N, q, and k all positive integers), then either k ? log N or N = 1.

(c) Give an efficient algorithm for determining whether a positive integer N is a power. Analyze its running time.