Why does is_prime fail for some numbers?

Question

Why does is_prime fail for some numbers?

If your code is failing for some numbers, it’s likely because you’re `return`ing too soon, or because you’re `return`ing the wrong thing in the wrong place. Without giving away the answer, take a look at the example control flow pseudo code below:

``````# From hint: any number less than 2 is not prime
if x is less than 2:
return x is not prime

# This loop is where we put our number to the test and return False
# so the function exits immediately if x isn’t prime
for n from 2 to x:
if x is evenly divisible by n:
return x is not prime

# If we made it here, our number must be prime because none
# of the other return statements were executed!
return x is prime
``````
1 Like

How is this code not returning 2 as False.

The loop does not run when x is 2, so it falls to the bottom return line.

1 Like

Sorry, I am not getting the for condition when x is 2. It should return false as 2%2 = 0.

1 Like

The parameters set in the range do not permit x to enter the loop if it is 2.

``````x = 2

range(2, x)  =>  (2..1)  =>  []``````
5 Likes

thank you, mtf…
didn’t consider that

1 Like

A post was split to a new topic: Don’t understand about why the solution works

9 posts were split to a new topic: Range in is_prime

2 posts were split to a new topic: Your function fails on is_prime(4)

Hi there, can anyone explain why we need to use (x- 1) as range? Thx

We don’t. That’s a misnomer of the author to indicate that range excludes the highest value, `x`.

``range(10)    # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]``
3 Likes

Oh right! Thanks mtf

1 Like

def is_prime(x):
if x < 2:
return False
if x == 2:
return True
for i in range(2, x):
if x % i == 0:
return False
else:
return True

Why is this returning your function fails on is_prime(9). It returns True when it should return False?

1 Like

If we may assume that `else` is on the `if`, then that is the problem. There is no default action if the above `return False` does not happen. Just continue the loop and have the function return True after the loop.

2 Likes

I am unsure what you mean by that. Returning True or False after the function does not change anything

2 Likes

If 9 is not divisible by 2 does that make it Prime? No. So why would we return True by default? That is why there is no else in the if statement.

``````  for ...:
if ...:
return False
return True
``````
5 Likes

That was just way more simple than I was thinking. It works perfectly. Thanks!

2 Likes

I kept getting hit by a lot of the default cases too. I didn’t know 1 wasn’t prime.
Anyway I guess it doesn’t matter, but the suggested solutions are super inefficient . I thought maybe something like this:

``````def is_prime(x):
if x < 2: return False
if x == 2: return True
if not x % 2: return False

test = 3
while test < (x / 2):
if not x % test:
return False
test += 2
return True
``````

No reason to go past half the numbers, or to keep checking even numbers over and over. I’m sure this could be made more efficient too. Finding the first million prime numbers or something shouldn’t really be that slow.

Generally speaking, it helps if we understand a concept before going headlong into solving a problem that relates to it.

At this stage of learning to program, efficiency would be the last thing to consider. First we learn to crawl, then to walk, then to fall down and get up again, then to run, in that order. The above code is still at the falling down stage.

The problem as devised for this exercise is meant to have a brute force solution. It is not a lesson in efficiency.

``````for n in range(2, x):
if x % n == 0: return False
``````

All even numbers get kicked out on the first iteration; we don’t need to test for evenness before the loop.

``````if x < 2: return False
for n in range(2, x):
if x % n == 0: return False
return True``````
6 Likes

You’re right, I know efficiency wasn’t really the point of the problem. But especially with prime number detection, efficiency is something that kinda interests me.

Just to be clear on this one. I know for even number `x` it will get resolved fast. What I meant was that, for example, if your’e testing `101`, you’ll iterate through `test` as `3, 4, 5, 6, 7, 8, 9` etc. I was suggesting cutting it down to only check `3, 5, 7, 9` as divisors, hence the `test += 2` . That cuts out ~ half the time.

Edit:
In fact, when I think about it, you should only need run `test` up to `sqrt(x)`, rather than `x/2`, since we only really need to find the first half of the divisors (for 21, we only need to find [3,7], don’t need to find [7,3] as well).
Sorry, I know that’s well past the scope of the problem!

1 Like