Why does is_prime fail for some numbers?

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

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

1 Like

The effective range has been well discussed on the forums, and yes, the square root is all we need, plus 1 so the top value is in the range. It is not the half way point, though, but the crossover point if we take a list of factors and overlay it with a reverse of that list. Moot, though. Good that you picked up on this.

I agree that we should only iterate over odd numbers, and we can go down this rabbit hole to elliminate numbers divisible by 3, 5, 7, etc. Ultimately this will reduce to a range that includes only Prime numbers. We are a long way from working on that level of complexity. First we walk, then we run. Don’t let this distract you from the lesson plan, but add it to the back burner for extra study when you complete the track.

1 Like
File "python", line 10, in <module>
  File "python", line 6, in is_prime
ZeroDivisionError: integer division or modulo by zero

Is the error for this code

def is_prime(x, n):
  if x < 2:
    return False
  for n in range(x):
    print n
    if x%n >= 1:
      return False
    else:
      return True
print is_prime(10, 2)

I don’t know why it’s dividing by zero. I tried to make it start at 2.