0

Hi i'm making a function that checks if a number is a prime or not but its telling me that 9 is a prime.

def eprimo(num):
    if num < 2:
        return False
    if num == 2:
        return True
    else:
        for div in range(2,num):
            if num % div == 0:
                return False
            else:
                return True
6
  • What is the question?
    – Alexis
    Oct 15, 2013 at 15:30
  • 1
    Step through your code. What have you tried?
    – UpAndAdam
    Oct 15, 2013 at 15:31
  • Just as an efficiency note you only need to test from 2 to num/2 Oct 15, 2013 at 15:31
  • 3
    (num ** .5) +1 or math.sqrt(num)+1 actually.
    – Synthetica
    Oct 15, 2013 at 15:32
  • protip: on the first line of eprimo put import pdb; pdb.set_trace() - here is a pretty decent tutorial if you need it. Oct 15, 2013 at 15:33

3 Answers 3

6

Your for loop exits right after the first iteration when it checks whether your number is divisible by 2. If your number is even, it will return False; otherwise, it will return True.

The solution is not to return True immediately; wait for the end of all the iterations in the loop instead:

for div in range(2, num):
    if num % div == 0:
        return False
return True

Alternatively, use the all() construct:

return all(num % div != 0 for div in range(2, num))
2

You're going to return from the first iteration of that for loop whether you're done checking or not. You shouldn't return from inside the loop unless the number is definitely not prime. Remove the else and only return True if the loop finishes.

def eprimo(num):
    if num < 2:
        return False
    if num == 2:
        return True
    else:
        for div in range(2,num):
            if num % div == 0:
                return False
        return True

Optimization side note: You really don't need to check all the divisor candidates up to num. You only need to check up to the square root of num.

0

Instead of testing all divisors in range(2,num), you could extract the test for even numbers and then loop only on the odd numbers. Additionally, as Bill the Lizard suggests, you could stop at the square root of num. This will be twice as fast:

def eprimo(num):
    if num < 2:
        return False
    if num % 2 == 0:
        return num == 2
    div = 3
    while div * div <= num:
        if num % div == 0:
            return False
        div += 2
    return True

Not the answer you're looking for? Browse other questions tagged or ask your own question.