slow script trying to find unique values in list
<p>I've got a problem in Python:
I want to find how many UNIQUE <code>a**b</code> values exist if:<br>
&nbsp;&nbsp;&nbsp;&nbsp;<code>2 â¤ a â¤ 100</code>and <code>2 â¤ b â¤ 100</code>?</p>

<p>I wrote the following script, but it's too slow on my laptop (and doesnt even produce the results):</p>

<pre><code>List=[]
a = 2
b = 2
c = pow(a, b)
while b != 101:
    while a != 101:
        if List.count(c) == 0:
            List.append(c) 
            a += 1
    b += 1
print len(List)
</code></pre>

<p>Is it good? Why is it slow?</p>

<p>Your code is not good, since it does not produce correct results. As the comment by @grael pointed out, you do not recalculate the value of <code>c</code> inside the loop, so you are counting only one value over and over again. There are also other problems, as other people have noted.</p>

<p>Your code is not fast for several reasons.</p>

<ol>
<li><p>You are using a brute-force method. The answer can be found more simply by using number theory and combinatorics. Look at the prime factorization of each number between 2 and 100 and consider the prime factorization of each power of that number. You never need to calculate the complete number--the prime factorization is enough. I'll leave the details to you but this would be much faster.</p></li>
<li><p>You are rolling your own loop, but it is faster to use python's. Loop <code>a</code> and <code>b</code> with:</p>

<pre><code>for a in range(2,101):
    for b in range(2,101):
        c = pow(a, b)
        # other code here
</code></pre></li>
</ol>

<p>This code uses the built-in capabilities of the language and should be faster. This also avoids your errors since it is simpler.</p>

<ol start="3">
<li>You use a <em>very</em> slow method to see if a number has already been calculated. Your <code>if List.count(c) == 0</code> must check every previous number to see if the current number has been seen. This will become very slow when you have already seen thousands of numbers. It is much faster to keep the already-seen numbers in a set rather than a list. Checking if a number is in a set is <em>much faster</em> than using <code>count()</code> on a list.</li>
</ol>

<p>Try combining all these suggestions. As another answer shows, just using the last two probably suffice.</p>

python