javanewbie - 2 months ago 11

Python Question

`print "Type a number"`

num = int(raw_input("> "))

if num % 2 == 0:

print "This is not a prime number"

else:

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

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.