如何使完美幂算法更有效？

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年之前是完美的，因为我在内存中存储了太多。我该怎么做才能让它对大量的人（比如5万或10万人）有效地工作呢。我试图在找到一个案例后结束它，但是如果数量很大，我的算法仍然效率太低。在

有什么提示吗？在

Answer 1

迭代检查“它有平方根吗？”？它有立方根吗？它有第四个根吗？…”你将很快到达假设根必须在1和{}之间的点，此时你可以停止。在

Answer 2

如果存在Ab和e，则一个数n是一个理想幂。例如216=6^3=2^3*3^3是一个完美的幂，但72=2^3*3^2不是。在

如果小于em>的幂是小于em>的，那么要知道这个数是的。此外，只需要测试素数的素数，因为如果一个数是复合指数的完美幂，那么它也将是复合分量素因子的完美幂；例如，2^15=32768=32^3=8^5是完美的立方根，也是完美的第五根。在

下面所示的函数isPerfectPower首先用牛顿方法计算整数根，然后对结果进行验证，以检查它是否等于n，从而测试每个小于log2n的素数。辅助函数primes用埃拉托斯thenes的筛子计算一个素数列表，iroot用牛顿法计算整数k次根，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

关于my blog的完全幂谓词还有进一步的讨论。在

Answer 3

相关的改进将是：

import math

def isPP(n):

        # first have a look at the length of n in binary representation
        ln = int(math.log(n)/math.log(2)) + 1

        y = []
        for i in range(n+1):
                if (i <= 1):
                        continue
                # calculate max power

                li = int(math.log(i)/math.log(2))
                mxi = ln / li + 1
                for it in range(mxi):
                        if (it <= 1):
                                continue
                        if i ** it == n:
                                y.append((i,it))
                                # break if you only need 1

        if len(y) <1:
                return None
        else:
                return list(y[0])