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>IIRC, it's far easier to iteratively check "Does it have a square root? Does it have a cube root? Does it have a fourth root? ..." You will very quickly get to the point where putative roots have to be between <code>1</code> and <code>2</code>, at which point you can stop.</p>

python algorithm python-3.x