How to make perfect power algorithm more efficient?
<p>I have the following code:</p>

<pre><code>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) &lt;1:
      return None
  else:
      return list(y[0])
</code></pre>

<p>Which works perfectly up until ~2000, since I'm storing far too much in memory. What can I do to make it work efficiently for large numbers (say, 50000 or 100000). I tried to make it end after finding one case, but my algorithm is still far too inefficient if the number is large.</p>

<p>Any tips?</p>

<p>a relevant improvement would be:</p>

<pre><code>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 &lt;= 1):
                        continue
                # calculate max power

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

        if len(y) &lt;1:
                return None
        else:
                return list(y[0])
</code></pre>

python algorithm python-3.x