javanewbie javanewbie - 9 months ago 46
Python Question

Why does prime number checker say 9 is a prime number?

print "Type a number"
num = int(raw_input("> "))

if num % 2 == 0:
print "This is not a prime number"

print "This is a prime number"

When I type '9' it says it's a prime number, which it isn't:

Type a number
> 9
This is a prime number

Is my code too simple? Is there something it doesn't check?

Answer Source

To check if is prime number you have to validate is it devisible by any number in range [2, sqrt(n)].

Following code does exactly the same:

import math

def is_prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

This method is good for small number, but if n is real big number then you need something faster. And in this case you can use Miller–Rabin primality test which checks primality with a certain probability.