Determine primes in given range

Question

I want to use Python to determine all prime numbers in a specified range, e.g. up to 20. I have the following code:

p = [ ]
for i in range(0, 20):
    for x in range(2, i):
        if i%x == 0:
            break
        else:
            p = p + [i]
            break
print p

The output is:

[3, 5, 7, 9, 11, 13, 15, 17, 19]

However, 15 and 9 are not primes. What am I missing?

score 2 · Accepted Answer · edited May 23 '17 at 12:13

The else branch is executed the moment you find a number that is not divisible by i. In this case that means any odd number is being added, as those are not divisible by 2, but all even numbers are. 9 and 15 may not be primes, but they are odd.

You should only add a number if the for loop has tested all integers in the range, not when the if test fails. You can do so by unindenting the else branch so that it matches up with the for loop.

Instead of matching with the if:

for ...:
    if ...:
    else:

match with the for loop:

for ...:
    if ...:
else:

because then it is only executed if the for loop was not ended using a break statement, e.g. when all numbers were tested and did not manage to divide x:

for i in range(0, 20):
    for x in range(2, i):
        if i%x == 0:
            break
    else:
        p = p + [i]

Note that the break can then be removed from the else suite, as by that time you are no longer in the loop.

Note that to find a prime number, you only need to test up to the square root of that number; if a x is divisible by a number i, then it'll also be divisible by all divisors of i. See Why do we check up to the square root of a prime number to determine if it is prime?

And adding a number to a list can be done with list.append() too, it is a little clearer than using the addinion operator with another list:

for i in range(20):
    if i < 2:
        continue  # not prime numbers either
    for x in range(2, int(i ** 0.5) + 1):
        if i % x == 0:
            # found a divisor, abort search
            break
    else:
        p.append(i)

Demo:

>>> p = []
>>> for i in range(20):
...     if i < 2:
...         continue  # not prime numbers either
...     for x in range(2, int(i ** 0.5) + 1):
...         if i % x == 0:
...             # found a divisor, abort search
...             break
...     else:
...         p.append(i)
... 
>>> p
[2, 3, 5, 7, 11, 13, 17, 19]

Determine primes in given range

1 Answers1