6. is_prime . Not a question, a Solution


#1

I understand that this is not a forum for statements but for questions, but this exercise seems to be the one where everyone stucks, not because the programming is challenging, but the concept of the prime number can sometimes lead to logic errors, rather than syntax ones.

Ok, fellow learners, if you are here you probably stuck on this one, and judging from the questions about it on this forum it's challenging.

Truth is, i was stuck on it for a day or two, but i got the idea today, and ofcourse I won't just post a code, I'll explain.

Step 1. Prime Number:
"A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself."
Which means, that it's not just a number that can't be divided by 2, as some people say. It means that it cannot be divided with any other number other than 1 and itself.

Step 2. What the exercise asks for:
The exercise wants us to create a function "is_prime" with x as an argument.
Then, we should check if x is EVENLY divisible by any number from 2 to x-1.
If it is, return False
If it's not divisible by any of them, which means that it's only divisible by 1 and itself, the return True

Step 3. Actual Code:

Let's start the code:

def is_prime(x): #function is_prime with argument x
    if x < 2: #A number less than 2 is not a prime number
        return False
    for n in range(2, x-1): #The loop, as the exercise asked for it, from 2 to x-1
        if x % n == 0: #if x is evenly divisible by n
            return False
    else: #See explanation for this one
        return True

Explanation
The else statement MUST NOT be nested under the if statement. It's a common mistake, and it's usually what ruins the exercise. Exercise hints that saying "If none of them are, then return True", which means that the for loop should end first, then if x wasn't evenly divisible with any of the n numbers, then you return True.

Common mistakes:
As you already saw, I did not use "if x == 3" or "if x == 2". Even though range(2, x-1) for x = 2 and x =3 returns an empty list, the program still works, since the for loop will not return anything, and else will go ahead and give us True, and 2 and 3 are both prime numbers.

So, you don't need these if statements

Hope I helped, please feel free to ask me if something bothers you :slight_smile:


#2

Great! Thanks a lot!


#3

Mate thanks for taking time sharing this with us although I've not yet figured out how I'm supposed to make this work without defining conditions using 'if / else' lol


#4

Thank you! My code wasn't working because my else statement was under the for loop. I'm still a little unclear on that however, why exactly does it not work with that?


#5

Thanks! This was really helpful! My else was nested under my if, so that's why I failed


#6

def is_prime(x):
for n in range( 2 , x-1):
if x % n == 0:
return False
else :
return True
this is what i hv done!
i mean is it neccesarry to add if x < 2: #A number less than 2 is not a prime number
return False...it'll anyway result false if it is nt prime.. what is the use of adding ?


#7

Shouldn't the range be something like range(2, x) as the x is not included in the range?


#8

I am confused for the same. why else statement shouldn't be under the for loop


#9

So, I see that people are still a bit unclear on that. I'll try to explain one more time
Again, prime number: a positive integer greater than 1 that has no positive divisors other than 1 and itself.
"No positive divisors other than 1 and itself"
That means that for a number to be prime, it must not be evenly divisible by any number other than 1, and itself.

So, we must check EVERY possible positive number, from 2 (because if it's divisible by 1 it's fine) until x - 1 (which I am still not sure why it's x-1, probably because it's pointless to check the number before x, since it will obviously not be evenly divisible by it) in order to test if x is EVENLY divisible by it. If it is, even with ONE of them, we return False, else we return True. The else statement MUST be under the for loop and NOT nested in it. Why is that? Because we must check EVERY single number in that range. If we nest the else, the for loop will either return false if the number is not divisible by 2, and if thats not the case, it will not check the next number in the range, it will just proceed to the else statement and return True.

Remember that when the if arguments are not True, the else will be executed, and in this case, we don't ant the else to be executed UNLESS we are done with the for loop

Thats the best I could do, I' sorry if you still dont get it :confused:


#10

Check my reply to jhun337 above


#11

Well, I guess it's useless to check if a positive number x is evenly divisible by the number before it, since no positive number above 2 is evenly divisible by x-1. That's why we end the loop 2 numbers before x.


#12

Your code seems to raise an error
"Oops, try again. Your function fails on is_prime(0). It returns True when it should return False."
I pasted this in the editor and it didn't seem to work:

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

As you can see, you need the x<2 if statement, because numbers lesser than or equal to 3 will give as range(2, x-1) an empty list. That means that the code will end up going to the else statement and return True. That's ok for 2 and 3, because they are prime numbers, but it messes up numbers less than 2, returning them ALL true. So, you better add that if statement in the beginning :wink:


#13

thhhhhhhhhhhhhank you :slight_smile: :slight_smile: :smile:


#14

Great Post. Your solution works perfect :slight_smile :slight_smile: Amost identical to mine.

Althought CC asks us to use x-1online 4 I don't think it's necessary. I believe Python's range automatically does x-1 for us and that just x will work as well. For example, my code for that line was for n in range(2, x)

CC accepts both ways as a correct answer, but being new to Python, can anyone confirm if I'm correct so I don't provide wrong info, and also explain if there is a reason why it's better to use x-1 that I may be over-looking?

Thanks in advance :slight_smile:


#15

Thanks for giving a great explanation


#16

I thought the range(a,b) was not inclusive on the ending range, so if we want to try dividing x by numbers ranging from 2 to n-1 the range should be (2,n). isn't it?

My second question concerns is_prime(2), 2 is a prime but I think in your scenario is_prime(2) would return False no? 2%2=0
Shall we insert a specific if scenario for 2?


#17

I have answered all of your questions above. Please take the time to read carefully, its the main reason people make mistakes.

Range is not inclusive on the ending range, thats right, but I explained, that there is NO point to check if a number is evenly divisible by the number before it ( x % (x-1) == 0 ) because only 2 can do that, and we dont care about 2 (ill explain that later). So, we take a range till x-1, which means that we stop TWO numbers before the one we are testing to see if its prime.

Have you tested the algorithm? It obviously works, so it also works for is_prime(2), I wouldnt post a non working algorithm as a solution.

I explained is_prime(2) above:

Now, I will explain it, one last time.

range(2, 2-1) equals an empty list ( [] ). Same happens with is_prime(3) and range(2,3-1)

THAT MEANS: We do not have ANY list to iterate, so, the program leaves the for loop and goes to the else statement under it. returning True, and its correct, since 2 and 3 are prime numbers.

I'll ask all of you who are ready to ask me another question to CAREFULLY read the solution and all my replies and THEN ask me a question. Im happy to answer all of your questions, I am not happy to answer the same thing repeatedly.


#18

Not sure if I answered you before, but there you go:


#19

Hi, small question.

So when you format the 'for' statement and put it on the same indentation level as the first If statement, why is that? Does it just read the statements separately? I didn't realise you can break up if/elif/else statements.


#20

You don't always need an else/elif statement under an if statement.

An if statement executes only if the arguments you provide are True. In this case, if the number x is less than 2, then the argument x<2 is True, and the if is executed. Then you return False, and the program ends.

If the arguments you provide are False, then the if statement (obviously) DOES NOT execute and
the code just goes on to execute the next line. In this case, if the number x is not less than 2, then the code goes on with the for loop that handles all the other numbers greater than or equal to 2.