Why does is_prime fail for some numbers?


#1

Question

Why does is_prime fail for some numbers?

Answer

If your code is failing for some numbers, it’s likely because you’re returning too soon, or because you’re returning 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

FAQ: Learn Python - Practice Makes Perfect - factorial FAQ: Learn Python - Practice Makes Perfect - is_prime
#2

How is this code not returning 2 as False.


#3

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


#4

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


#5

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)  =>  []

#6

thank you, mtf…
didn’t consider that


#7

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


#8

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


#16

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


#18

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


#19

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]

#20

Oh right! Thanks mtf


#21

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?


#22

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.


#23

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


#24

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

#25

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


#26

I kept getting hit by a lot of the default cases too. I didn’t know 1 wasn’t prime. :slight_smile:
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. :sweat_smile:


#27

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

#28

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. :stuck_out_tongue_winking_eye:

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!