检查一个数字是否是另一个数字的完美幂次 [英] Check if a number is a perfect power of another number

问题描述

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

For example, 243 is a perfect power of 3 because 243=3^5.

我以前一直在使用(math.log(a) / math.log(b)).is_integer()，我认为它工作正常，但是后来我在上面的示例中进行了尝试，由于浮点运算，它实际上返回4.999999999999999.因此，只有极少数数字(少于我发现的大约100个)才可靠.

I've previously been using (math.log(a) / math.log(b)).is_integer(), which I thought worked fine, but then I tried it with the example above and it actually returns 4.999999999999999 due to floating point arithmetic. So it's only reliable for very small numbers, less than around 100 I've found.

我想我可以使用循环进行重复乘法...即将i设置为3，然后9，然后27，然后81，然后243，这等于目标，所以我们知道这是一个完美的幂.如果它达到大于243的程度，那么我们知道它不是完美的力量.但是我实际上是在循环内运行此检查，因此这似乎效率很低.

I suppose I could use a loop to do repeated multiplication... i.e. set i to 3, then 9, then 27, then 81, then 243, which equals the target, so we know it's a perfect power. If it reaches a point where it's bigger than 243 then we know it's not a perfect power. But I'm running this check within a loop as it is, so this seems like it'd be very inefficient.

那么还有其他方法可以可靠地检查一个数字是否是另一个的完美幂吗?

So is there any other way of reliably checking if a number is a perfect power of another?

推荐答案

尝试:

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

也就是说，仅使用log()(请注意有2个参数的形式！)来获得整数幂的猜测，然后验证是否可行".

That is, only use log() (note there is a 2-argument form!) to get a guess at an integer power, then verify whether "that works".

请注意，即使整数参数太大而不能表示为浮点数，math.log()也会返回明智的结果.还要注意，Python中的整数**是精确的，并且在内部使用了高效的算法(进行与指数位数成正比的乘法运算).

Note that math.log() returns a sensible result even for integer arguments much too large to represent as a float. Also note that integer ** in Python is exact, and uses an efficient algorithm internally (doing a number of multiplications proportional to the number of bits in the exponent).

与重复划分相比，这是简单明了的方法(通常)，效率更高.

This is straightforward and much more efficient (in general) than, say, repeated division.

但是我在回答您提出的问题;-)如果您有其他疑问，其他一些答案可能更合适.

But then I'm answering the question you asked ;-) If you had some other question in mind, some of the other answers may be more appropriate.

这篇关于检查一个数字是否是另一个数字的完美幂次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！