6/15. is_prime()


#1

Hello,

Same assignment, different problem.

Somehow it stops giving the right answer for number 9?

def is_prime(x):
    if x == 0 or x == 1:
        return False
    elif x == 2:
        return True 
    else:
        for n in range(2,x):
            if x % n == 0:
                print "not a prime"
                return False
            else:
                return True

If x is 9, and n is picked from 2 to 9, as it starts dividing through numbers, as soon as it encounters 3 it should say 9 % 3 == 0, and print "not a prime" and return False. But I keep getting this error:

Oops, try again. Your function fails on is_prime(9). It returns True when it should return False.


#2

The issue here is that you want to keep testing if the current iteration of n is not divisible evenly, but when you find even one instance where it divides, you want to break out and declare that the number is not prime.

So, you want to have your loop return false when the condition is known to be false, but CONTINUE if the condition is true.

If you reach the final iteration without having returned, then and only then can you return true.

This solution here works, but that final test is not explicitly needed, you could just return True if you end the for loop without having returned false, but I added it for clarity:


#3

So my problem was using an else statement instead of another for, which made it end prematurely? I still don't think I quite get why mine wasn't correct.

I get why yours is good, but I don't see what was wrong with mine just yet.


#4

So the problem with your solution is the "return True" as an ELSE condition.

Think about what happens in a number like 9:

9 % 2 != 0
9 % 3 == 0 #This is the important case!
9 % 4 != 0
9 % 5 != 0
9 % 6 != 0
9 % 7 != 0
9 % 8 != 0

What happens in your code, is that it tests the first condition: 9 % 2 == 0 which is FALSE, and then it executes the ELSE statement, causing it to immediately return TRUE! Remember that a return is like a break, it will break out of the loop and never execute another iteration of the loop.

It never continues the loop, so it never gets a chance to test 9%3 == 0, which would have caused it to "return False".

That is why it mistakenly labels 9 as prime, because it runs only one test, and then says "Yup, 9 must be prime".

In my code, it gets a chance to test the "not prime" condition for every number from 2 to N-1, if it finds one, it returns "FALSE" and bails out.

IF not though, it just keeps right on testing all of the other numbers in that range.

Only when it has tested every number from 2 to N-1 can it then say "Yeah, I found no even divisors for 9 from 2 to 8, so 9 is therefore prime".

:smile:


#6

You could also move your last else to be under for loop, and change range to end at x-1, like that,:

so if for loop ends without returning False, else statement will be done


#7

Ok, that's a really clear explanation, thanks a lot! :smile:


#8

My pleasure, I hope it helps. I really like Codeacademy and while I'm far from a Python expert (its really not hard to concoct somewhat obtuse python code that I cannot read) when it comes to foundational, procedural stuff like this, its usually something I can handle.

For example, these "gotcha" type questions found here: http://www.toptal.com/python/interview-questions

Those are the kinds of questions I end up puzzling over for a while. Some of them are highly tricky and require knowledge of some of the more esoteric functions of Python that you may never encounter in common applications of the language (but this of course, depends on the kind of work you are doing).


#9

I was really confused on this question and your reply helped me pass it, I was wondering if you could explain the code with the instructions so that i understand it?


#11

Can you refine your question a little? I'm not sure if you are asking for me to break down the solution, or the problem.

Every problem in computer science is solved via the following process:

Clear problem definition.
Algorithm selection / creation.
Data structure choice.
Implementation.
Testing.

So, I guess I'm asking which of the steps above you are struggling to understand, I would be happy to help with any of them.