Decomposing a number N into composite factors (e.g., 2059 2971) is generally understood to be a hard problem for large values of N. For some N of specific forms, factoring can actually become quite easy: observing that 40467 2262-1032, we have via the difference of squares formula 40467 2262 - 1032 - (226 - 103) * (226 +103)-123 *329 One special case of an easily factorable number is when N is a perfect power of some integer base, i.e., N-a* for some integer a, k> 1. Consider the question, "is N 10200 a perfect square?" One way to check might be to compute the square root. Since V10200 100.995, as the fractional part is not 0, N cannot be a perfect square. This, however, requires computation over the real numbers, a topic largely untouched in this course. The goal of this problem is to approach this computation, purely in terms of integer arithmetic. In each of the following, when we ask for a big-O bound, we are interested in as tight an upper bound as you can justify