Python, prime number checker

Question

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

Just as an efficiency note you only need to test from 2 to num/2 — ford prefect, Oct 15 '13 at 15:31
protip: on the first line of `eprimo` put `import pdb; pdb.set_trace()` - [here](http://pythonconquerstheuniverse.wordpress.com/2009/09/10/debugging-in-python/) is a pretty decent tutorial if you need it. — Wayne Werner, Oct 15 '13 at 15:33
@Synthetica one of my most favorite "hacks" - getting the square root without having to use `math.sqrt()` — Wayne Werner, Oct 15 '13 at 15:34

score 6 · Answer 1 · answered Oct 15 '13 at 15:31

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))

Bill the Lizard · Accepted Answer · 2013-10-15T15:36:20.113

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.

user448810 · Answer 3 · 2014-02-10T18:18:11.680

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

Python, prime number checker

3 Answers3

Linked

Related