有效地计算整数 n 的对（基数，指数）表示

Question

我在设计一种方法来将整数 n 表示为整数对（底数、指数）以便 n == base ^ exponent 进行赋值时遇到问题。以下是该方法的合同。 @pre 指定 n 必须是什么，@post 定义输出必须是什么。

/**
* 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){}

其中 class Power 只是一个 Pair 实例。

我已经设法使用一种天真的方法解决了这个问题，在这种方法中，我通过计算 log(n) / log(b) 和 2 <= b <= sqrt(n) 来计算底数和指数的值。但是作业描述说我必须产生一个优雅而高效的方法，但我找不到更有效地计算它的方法。

Answer 1

在查阅了一些书籍后，我设计了以下解决方案：

输入整数 n:
设 p₁...p_m 是 m 个唯一素数。
那么我们可以将n表示为：

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

然后计算 e₁ ... e_m 的 gcd d 使用欧几里德算法。
那么我们将n表示为：

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

现在我们有：

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

e=d
return 新幂(b, e)

有效地计算整数 n 的对（基数，指数）表示

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

java

decomposition