Getting wrong answers for prime numbers

Question

I'm getting several incorrect answers in this code. For example, 9 is showing as prime. I'm guessing my problem is with using the breaks, but I can't seem to logically figure out what is wrong with this simple code someone asked me about.

for number in range(0, 1000):

    for x in range(2, number):
         if (number % x == 0):
             break
         else:
             print x
             break

Answer 1

In your script, regardless of if the number is divisble by 2 or not, it breaks the loop immediately. I've reindented the code and this is probably closer to what you were trying to do.

In your original code, if the number is divisible by 2 (first number in the range(2,number), then you break the loop and if it is not divisible you also break the loop. So all odd numbers, like 9, looked like primes.

The else keyword after a for loop is run iff the loop exits normally. So the "is prime" part will only be printed if no divisor is found.

for number in range(0,1000):
    for x in range(2,number):
        if(number % x == 0):
            print number,"divisible by",x
            break
    else:
        print number, "is prime"

You can see this is anction here: http://codepad.org/XdS413LR

Also, this is a naive algorithm (not a critique of the code, exploring simple algorithms is a useful study), but you can make a little more efficient. Technically you only need to check as far as the sqare root of number, as any number larger than the square root must have a complement that is less than the square root, which should have already been encountered. So the logic in the code can be changed to:

from math import sqrt
for number in range(0,1000):
    for x in range(2,int(sqrt(number/2))):
        # Rest of code as above.

That said there are many ways that you can optimise the checking or discovery of prime numbers that are worth investigating if you get the chance.