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>Try this Newton's method:</p>

<pre><code>def NthRoot(k, num):
    i, j = num, num+1
    while i &lt; j:
        j = i
        t = (k-1) * j + num // pow(j, k-1)
        i = t // k
    return j

print(NthRoot(3,125))
</code></pre>

<p><a href="https://en.wikipedia.org/wiki/Newton&#39;s_method" rel="nofollow">https://en.wikipedia.org/wiki/Newton's_method</a></p>

python algorithm python-3.x