326. Power of Three

Posted on | In |

LeetCode 326. Power of Three

如题所述，对于判断一个数$n$是否是任意一个质数$a$的指数的问题，我们都可以用以下方法来求。

  • 找到整数范围内能表示的最大的这个质数的指数$max$。

  • 用$max$对$n$取模，如果模为0则结果为真，否则结果为假。

代码如下。

1
2
3
4
public boolean isPowerOfThree(int n) {
    int max = (int) Math.pow(3, (int) (Math.log(Integer.MAX_VALUE) / Math.log(3)));
    return n > 0 && max % n == 0;
}

为什么要求$a$必须为质数，原因是如果$a$不为质数，那么这个判断会将不符合条件的数误判为真。例如：$a = 9$，$n = 27$，显然$n$不是$a$的指数。假设$max$是int范围内，最大的$a$的指数，那么 $max= 9^b$。$max \mod n = (3^{2b}) \mod (3^3) = 0$，从而得出错误结果。