Why does my prime number algorithm need a break in the for loop?

Question

I wrote an algorithm that populates a list with the first 1000 primes.

When I run it like this, it populates the list with some numbers that aren't prime.

def is_prime():
    primes = [2]
    a = 0
    x = 3
    while a < 999:
        for i in range(2, x):
            if (x % i) == 0:
                x += 2
                break
        else:
            primes.append(x)
            a += 1
            x += 2
    return primes


print is_prime()

Please properly indent your code. – James Mills Jan 13 '14 at 04:37 — James Mills, Jan 13 '14 at 04:37
and perhaps not post exactly same code? – Mitch Wheat Jan 13 '14 at 04:38 — Mitch Wheat, Jan 13 '14 at 04:38
What are the values you weren't expecting? – Christian Tapia Jan 13 '14 at 04:40 — Christian Tapia, Jan 13 '14 at 04:40

score 2 · Answer 1 · edited Jun 20 '20 at 09:12

[Why does this] need a break in the for loop?

Let me quote this tutorial you might want to look at:

Loop statements may have an else clause; it is executed when the loop terminates through exhaustion of the list (with for) [...], but not when the loop is terminated by a break statement.

This means that in your while-loop,

 primes.append(x)
 a += 1
 x += 2

is only executed if the for-loop has iterated over all i in range(2, x) and never once encountered break. (This means, that there was no divisor of x found)

Without the breakstatement the code above would be executed in every iteration of the while-loop. Therefore, without the break statement you just add 2 to x every time you find a divisor of x and claim that x is prime as soon as you reach the end of range(2, x) (note that in the range expression it's the original x before you started adding 2). This seems to work for small numbers but is not the same as checking if x has any divisors.

score 0 · Answer 2 · edited May 23 '17 at 11:43

Your algorithm seems to work.

For example, compare to a more standard approach:

def rwh_primes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

p0 = is_prime()  # OP's code
p1 = rwh_primes(7920)

print p0==p1   # prints True, so the lists are equal

Why does my prime number algorithm need a break in the for loop?

2 Answers2