如何让完美的幂算法更加高效？

我有以下代码：

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）。我在找到一个案例后试图结束它，但如果数字很大，我的算法仍然太低效。

有小费吗？

一个号码n是一个完美的幂，如果存在b and e为此b^e = n。例如，216 = 6^3 = 2^3 * 3^3 是完美幂，但 72 = 2^3 * 3^2 不是。

确定一个数是否是完全幂的技巧是知道，如果该数是完全幂，则指数e必须小于 log2n， 因为如果e大于 2^e将大于n。此外，只需要测试素数es，因为如果一个数是复合指数的完美幂，那么它也将是复合分量的素因子的完美幂；例如，2^15 = 32768 = 32^3 = 8^5 是一个完美的立方根，也是一个完美的五次方根。

功能isPerfectPower如下所示测试每个小于 log2 的质数n首先使用牛顿法计算整数根，然后对结果求幂以检查它是否等于n。辅助功能primes通过埃拉托斯特尼筛法计算素数列表，iroot计算整数k通过牛顿法求 th 根，并且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.