Why does this "Is_Prime" function fail on 9, 15, and 21?


#1

This is the function I originally wrote:

def is_prime(x):
    if x < 2:
        return False
    elif x == 2 or x == 3:
        return True
    else:
        for n in range(2, x-1):
            if x % n == 0:
                return False
            else:
                return True

I understand to correct this function and make it work I need to remove the last "else" statement and fix the indentation for the last "return True". What I do not understand is why the function I pasted above works on most numbers but fails when you pass it 9, 15, and 21 (21 being highest number I tested it to). What is it about the improperly formatted else & return true statements that cause the function to return the proper result for say 17, 18, 19, and 20, but then fail for 21?


#2

May I tell you which lines to delete? Then we can give pause, and you may arrive at the solution quite readily.


#3

Thank you for your response. I know if I delete the last "else" and move the last "return True" to align under the other "else" statement it works. I was primarily just confused as to why this incorrect version works most of the time, but fails on specific numbers. What is the function doing that causes it to work sometimes, but fail other times?


#4

Because:
17 is a prime-number and not divisible by 2 (without remainder) --> else branch return True (but you didnt tested all other numbers)
18 is no prime-number and divisible by 2 --> if branch return False
19 is a prime-number ....
just try it on your own for other numbers

it only works for numbers that are divisible by 2 and are no prime-numbers, but you already observed that it dont work for non-prime-numbers, that are not divisible by 2 but by 3 for example (9, 15 ...)


#5

The else branch in the if statement is the cause. It should not be there. Remove the else and slide the return True over to the left of the code block (in line with the for).


#6

Hi!

Hi, thats simple, because we want the for cycle to run all the numbers in range before taking a conclusion (i.e. screening for x % n == 0). Once and if this condition is True, then it should exit the for cycle and return True outside the cycle.

If you dont do that (and put return True within for for cycle), it will take 9%2 = 4.5, it will go to else (if you indent as you did) and return True. And we dont want this, right? Because 9 is not a prime number.

So it has to ignore the 2 and continue to the next number, which is three. Now it will run 9%3 = 0, so it will exit the loop because this should be False. That's why we cannot have the return True statement INSIDE the for loop.

I hope it is clear, it took me a while before coming up with this answer!

Cheers,
M


#7

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.