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

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?

Because this is not a prime number checker. You're basically checking even or odd, and 9 is odd. — FatalError, Nov 16 '16 at 16:02
Your program asks "is this number divisible by 2? If not, it's prime". That's why it counts 9 as a prime. Perhaps look into the [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) for a simple prime checker? — Aurora0001, Nov 16 '16 at 16:02
Your code doesn't check prime numbers, it checks if a number is even or odd. — user2393256, Nov 16 '16 at 16:02
Your program is only checking if the number inputted is divisible by 2 or not. Which actually checks for even number. Not prime. — Imtiaz Raqib, Nov 16 '16 at 16:03

score 4 · Answer 1 · answered Nov 16 '16 at 16:02

You're only checking if it is an even number, by checking if it is divisible by 2. But 9 is divisible by 3 so you need to check that also. The easiest way would be to check all numbers up to the square root of the number you're checking for primality.

score 4 · Answer 2 · answered Nov 16 '16 at 16:05

All you are doing here is checking whether or not a number is evenly divisible by 2. Since 9 / 2 = 4.5, it's not evenly divisible by 2 thus going to the else clause.

Here is a condensed, working version of what you probably want:

def is_prime(a):
    return all(a % i for i in xrange(2, a))

neverwalkaloner · Accepted Answer · 2016-11-17T01:10:04.063

2

To check if number is prime 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.

edited Nov 17 '16 at 01:10

answered Nov 16 '16 at 16:15

neverwalkaloner

46,181
7
92
100

Why `int(math.sqrt(n))+1)`? – javanewbie Nov 16 '16 at 16:19
range(x, y) returns interval [x, y) (excluding y) but you also need to check value sqrt(n) so you can say range(x, y+1) and now y will included into validation too. – neverwalkaloner Nov 16 '16 at 16:32
But why square root of the number in question? – javanewbie Nov 16 '16 at 16:39
Because you dont have to validate all numbers from 2 to n. If n is not prime number and one of its dividers is greater than sqrt(n) then another one is smaller, so trying dividers from 2 till sqrt(n) you may find all dividers of number n (even greated than sqrt(n)). – neverwalkaloner Nov 16 '16 at 16:47
Thanks, I understand now. – javanewbie Nov 16 '16 at 16:51

score 1 · Answer 4 · edited May 23 '17 at 12:13

1

You are checking if a given number is even or not, and 9 is not even so your code prints out "This is a prime number"

Please take a look at this Stackoverflow question for a detailed explanation on how to check for prime numbers using Python.

edited May 23 '17 at 12:13

Community

1
1

answered Nov 16 '16 at 16:10

McMutton

905
13
25

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

4 Answers4