How to append to a list only the first time a prime is encountered

Question

I wrote this Python code to print all the prime numbers until 1000:

primes = []

for prime in xrange(1, 1000):
    for b in xrange(2, prime):
        if (prime % b == 0):
            break
        else:
            primes.append(prime)

print primes

However, if a number is a prime, it is appended a lot of times before moving to the next number. I tried using continue instead of break but that does not work.

I also added some more code onto that (which works) to simply output the array into a text file. It is so large that I cannot even paste it into here.

How can I append each prime number to the list only once instead of many times?

Answer 1

There's a feature in Python you can use quite effectively here. Just change your indentation like this:

primes = []

for prime in xrange(1, 1000):
    for b in xrange(2, prime):
        if (prime % b == 0):
            break
    else:
        primes.append(prime)

print primes

That is, de-indent the else clause. This way it is not the else of the if but of the for loop. A for loop can have an else branch which gets executed after the loop has performed all scheduled iterations. If there is a break called, it gets not executed.

You can use that here without having to change a lot of your original code.

Of course, in your original version, each loop iteration in which a tested number did not turn out to be a non-prime, that tested number got appended (which was not what you wanted).

Also note that 1 is not a prime number (at least since Gauss in 1801, some say even since Euclid (600BC) first wrote about prime numbers, although there were heretics since into the 19th century), so your outer loop should start at 2 instead.

But note what Daniel wrote in his answer; you do not have to step through all the way to prime because after reaching the square root of prime, you can bail out. I always compared b * b to prime, but maybe computing sqrt(prime) once even is faster.

And of course, you can be faster by ignoring all even numbers completely. Except 2 none are prime ;-)

Answer 2

You need to only add the number if it reaches the end of the loop without it finding a divisor.

from math import sqrt

prime = True
for b in xrange(2, sqrt(prime)):
    if prime % b == 0:
        prime = False
        break
if prime:
    primes.append(prime)

Note I've added an optimization: you only need to test up the square root of a number, because anything after that can't possibly divide.