Efficiently computing a pair(base, exponent) representation of an integer n

Question

I'm having trouble with desiging a method to express an integer n as an integer pair (base, exponent) such that n == base ^ exponent, for an assignment. Below is the contract for the method. @pre specifies what n has to be, @post defines what the output has to be.

/**
* Writes a number as a power with maximal exponent.
*
* @param n  the number to 'powerize'
* @return  power decomposition of {@code n} with maximal exponent
* @throws IllegalArgumentException  if precondition violated
* @pre {@code 2 <= n}
* @post {@code n == power(\result) &&
*     (\forall int b, int e;
*      2 <= b && 1 <= e && n == b ^ e;
*      e <= \result.exponent)}
*/
public static Power powerize(int n){}

Where the class Power is just a Pair instance.

I already managed to solve this problem using a naive approach, in which I compute the value of the base and exponent by computing log(n) / log(b) with 2 <= b <= sqrt(n). But the assignment description says I have to produce an ellegant & efficient method and I couldn't find a way to compute this more efficiently.

Answer 1

After consulting some books I designed the following solution:

Input int n:
Let p₁...p_m be m unique primes.
Then we can express n as:

n = p₁^e₁ x ... x p_m^e_m.

Then compute the gcd d of e₁ ... e_m using the euclidean algorithm.
Then we express n as:

n = (p₁^e₁/d x ... x p_m^e_m/d)^d.

now we have:

b = p₁^e₁/d x ... x p_m^e_m/d

e = d

return new Power(b, e)