如何使完美的功率算法更有效？

Question

我有以下代码:

def isPP(n):
  pos = [int(i) for i in range(n+1)]
  pos = pos[2:] ##to ignore the trivial n** 1 == n case
  y = []
  for i in pos:
      for it in pos:
          if i** it == n:
              y.append((i,it))
              #return list((i,it))
      #break
  if len(y) <1:
      return None
  else:
      return list(y[0])

直到〜2000年才能完美运行,因为我在内存中存储的太多了.我该怎么做才能使它有效地用于大数(例如,50000或100000).在找到一个案例之后我试图让它结束,但是如果数字很大,我的算法仍然效率太低.

有小费吗？

Answer 1

IIRC,所以可以非常容易反复地检查"是否有一个平方根是多少？它是否有一个立方根？是否有第四根？......"你会很快得到的地方,假定根必须的点1和2,此时你可以停下来.

Answer 2

许多Ñ是，如果存在一个完美的功率b和Ë为其b ^ ë = Ñ。例如 216 = 6^3 = 2^3 * 3^3 是一个完美的幂，但 72 = 2^3 * 3^2 不是。

确定一个数字是否是完美幂的技巧是要知道，如果这个数字是完美幂，那么指数e必须小于 log2 n，因为如果e大于那么 2^ e将大于n。此外，只需要检验素数e s，因为如果一个数是复合指数的完美幂，那么它也将是复合成分的素因子的完美幂；例如，2^15 = 32768 = 32^3 = 8^5 是一个完美的立方根，也是一个完美的第五根。

下面isPerfectPower显示的函数通过首先使用牛顿方法计算整数根来测试每个小于 log2 n的素数，然后为结果提供动力以检查它是否等于n。辅助函数primes通过埃拉托色尼筛计算素数列表，通过牛顿法iroot计算整数k th-root，并通过二进制搜索ilog计算以b为底的整数对数。

def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps

def iroot(k, n): # assume n > 0
    u, s, k1 = n, n+1, k-1
    while u < s:
        s = u
        u = (k1 * u + n // u ** k1) // k
    return s

def ilog(b, n): # max e where b**e <= n
    lo, blo, hi, bhi = 0, 1, 1, b
    while bhi < n:
        lo, blo, hi, bhi = hi, bhi, hi+hi, bhi*bhi
    while 1 < (hi - lo):
        mid = (lo + hi) // 2
        bmid = blo * pow(b, (mid - lo))
        if n < bmid: hi, bhi = mid, bmid
        elif bmid < n: lo, blo = mid, bmid
        else: return mid
    if bhi == n: return hi
    return lo

def isPerfectPower(n): # x if n == x ** y, or False
    for p in primes(ilog(2,n)):
        x = iroot(p, n)
        if pow(x, p) == n: return x
    return False

在我的博客上有关于完美幂谓词的进一步讨论。