0

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
pppery
  • 3,731
  • 22
  • 33
  • 46
trueCamelType
  • 2,198
  • 5
  • 39
  • 76
  • possible duplicate of [Shouldn't else be indented in the below code](http://stackoverflow.com/questions/12194947/shouldnt-else-be-indented-in-the-below-code) – Will Ness Sep 05 '13 at 16:41

4 Answers4

4

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.

  • 1
    Thanks for the quick answer, and also for the very thorough explanation of what exactly was wrong with the old code. Also for a way to make the code more efficient. – trueCamelType Sep 05 '13 at 04:09
  • 1
    @Slimmons If you are curious, a more efficient method for prime detection that is often used in algorithms courses is the [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) –  Sep 05 '13 at 04:16
  • 1
    Actually you only need to check as far as sqrt(number), not number/2. – sharcashmo Sep 05 '13 at 13:25
1

I think you want something like this:

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

this iterates through every number form 1-100 and checks if any number is divisible by any # besides one but you need the else: statement out side of the inner for loop so if it goes throught the inner for loop without finding a divisor its prime

Serial
  • 7,925
  • 13
  • 52
  • 71
1

Here are some alternatives. First, this checks for primes:

def check_for_prime(n):
if n == 1: return False
elif n == 2: return True
elif n%2 == 0: return False

# Elementary prime test borrowed from oeis.org/A000040.
odds = 3
while odds < n**.5+1:
    if n%odds == 0: return False
    odds += 2
return True

This is slightly faster, but you should have experience using yield:

def primes_plus():
yield 2
yield 3
i = 5
while True:
    yield i
    if i % 6 == 1:
        i += 2
    i += 2
Cawb07
  • 2,037
  • 3
  • 17
  • 22
1

Here are some alternatives.

n is the number till the range you want to find

n=100
for i in range(0,n):
    num = filter(lambda y :i % y == 0,(y for y in range(2,(i/2))))
    if num or i == 4:
        print "%s not a prime number" %(i)
    else:
        print "%s is a prime number" %(i)
Djay
  • 9
  • 2