找到给定范围内的所有A^x

Question

我需要找到A^X形式的所有单项式，这些单项式在m到{}之间。可以安全地说，基A大于1，幂X大于2，并且只需要使用整数。例如，在50到100的范围内，解决方案是：

2^6
3^4
4^3

我第一次尝试解决这个问题是对所有有意义的A和{}的组合进行暴力破解。但是，当在大范围内使用非常大的数字时，这会变得太慢，因为这些解决方案是在更密集的处理中使用的。代码如下：

^{pr2}$

我可以通过将值保存在临时变量中来删除一个base**power，但我不认为这会造成严重的影响。我还想知道使用对数是否更好，或者是否有一个封闭形式的表达式。我愿意接受任何优化或替代方案来找到解决方案。在

Answer 1

不要搜索；考虑端点。在

例如，所有带x == 3的解都是这样的，a位于{}的立方根和{}的立方根之间。所以计算这些立方根，并使用它们之间的整数范围。因为a至少是2，所以最大的x是{}的logbase2，所以这就是您知道何时停止的原因。在

from math import log, ceil, floor

def monoSearch(low, high):
    max_power = int(floor(log(high) / log(2)))
    for power in range(3, max_power + 1):
        min_base = low ** (1.0 / power)
        max_base = high ** (1.0 / power)
        for base in range(int(ceil(min_base)), int(floor(max_base)) + 1):
            yield '%s ^ %s' % (base, power)

print '\n'.join(monoSearch(42, 1000000))

不幸的是，由于浮点不精确，这可能会丢失一些值。在

Answer 2

利用log（x）是一个递增函数的事实：

m <= a^x <= n当且仅当log(m) <= x * log(a) <= log(n)

然后找到乘积在这个转换区间内的x，log(a)的数将更加容易。在

Answer 3

您可以使用多个二进制搜索对其进行优化。对于以下任何注释：

• 一旦达到一个幂次，使得base**power超过min所有幂p >= power满足{}->；你可以用二进制搜索最小幂
• 一个类似的参数证明您可以二进制搜索最大幂，这样base**power <= max
• 要找到最大基数，使base**power <= max对于任何power >= 3，还可以应用二进制搜索

现在，您可以像@wim所说的那样使用对数，但这要求您正在处理的数字可以用浮点表示，而使用二进制搜索只要您有任意精度的整数算术（Python也有）。在