CODEWITHSUNDEEP
pythonprimes
Do A Barrel Roll
Do A Barrel Roll

Reputation: 33

Prime number checker function is faulty

I wrote a function to calculate whether or not a number is prime, but try as it might, it just seems unable to give the correct response. It also prints the n value that is being incremented. Here is the code for the function (in Python, by the way):

def isPrime(x):
    for n in range(1, x):
        print n
        if x % n == 0:
            return False
    return True

If I input 

isPrime(17)

the function returns

1
False

What is going wrong here?

Upvotes: 3

Views: 1747

Answers (1)

João Silva
João Silva

Reputation: 91329

Every number is divisible by 1 and itself. A prime number is a natural number that has no positive divisors other than 1 and itself. Therefore, if you start your for-loop with 1, every number x will pass the condition x % 1 == 0 in the first iteration, returning False.

To fix it, you need to start your loop with 2 instead of 1. Also, as a side-note, you just need to loop from 2 to sqrt(x), since if there exists a number q > sqrt(x) that divides x, then there must also be a number p = x / q which also divides x, and p < sqrt(x).

Upvotes: 6

Related Questions