检查一个数字是否是另一个数字的完美幂

Question

例如，243是3的完美幂，因为243=3^5。

我以前一直在使用（math.log（a）/math。日志（b））。是_integer（），我认为它工作得很好，但后来我用上面的示例尝试了它，由于浮点运算，它实际上返回了4.99999999999。所以它只适用于非常小的数字，我发现不到大约100个。

我想我可以用一个循环来重复乘法。。。i、 将i设置为3，然后设置为9，然后设置为27，然后设置为81，然后设置为243，这等于目标值，所以我们知道这是一个完美的幂。如果它达到一个大于243的点，那么我们知道它不是一个完美的能量。但我在一个循环中运行这个检查，所以这看起来效率很低。

那么，有没有其他可靠的方法来检查一个数字是否是另一个数字的完美幂呢？

Answer 1

如果您要处理大量的数字，您可能需要查看gmpy2。gmpy2提供对GMP多精度库的访问。提供的函数之一是is_power（）。如果参数是某个基数的完美幂，它将返回True。它不会提供功率或基数，但它会很快过滤掉不可能是完美功率的数字。

>>> import gmpy2
>>> [n for n in range(1,1000) if gmpy2.is_power(n)]
[1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961]

一旦确定了可能的幂，就可以使用iroot\u rem（x，n）找到x的第n个根和余数。然后，一旦找到有效的指数，就可以找到基数。这里有一个例子，在一个范围内搜索所有可能的完美力量。

>>> for x in range(1,1000):
...   if gmpy2.is_power(x):
...     for e in range(x.bit_length(), 1, -1):
...       temp_root, temp_rem = gmpy2.iroot_rem(x, e)
...       if not temp_rem:
...         print x, temp_root, e
... 
4 2 2
8 2 3
9 3 2
16 2 4
16 4 2
25 5 2
27 3 3
32 2 5
36 6 2
49 7 2
64 2 6
64 4 3
64 8 2
81 3 4
81 9 2
<< remainder clipped>>

免责声明：我维护gmpy2。

Answer 2

可能是这样的：

def is_perfect_power(a, b):
  while a % b == 0:
    a = a / b
  if a == 1:
    return True
  return False

print is_perfect_power(8,2)

Answer 3

尝试：

b ** int(round(math.log(a, b))) == a

也就是说，只使用log（）（注意这里有一个双参数表单！）要猜测整数幂，请验证是否“有效”。

注意，math。log（）即使对于太大而无法表示为浮点的整数参数，也会返回合理的结果。还要注意，Python中的整数**是精确的，并且在内部使用了一个高效的算法（执行与指数中的位数成比例的乘法）。

这很简单，比重复除法更有效。

但我要回答你问的问题；-）如果你心里还有其他问题，其他一些答案可能更合适。