Is_prime error


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

So far, the code above is what I’ve been able to come up with for this exercise, but I keep getting an error message such as: Your function fails on is_prime(2). It returns None when it should return True. Could someone explain why this is so? Thank you!


#2

None is the default value returned by functions, so no return keyword is reached. Now read the error message again

If we want to return something other then None at the end of function, we can use a return keyword, but given return is the last thing a function does, the function ends when a return keyword is reached

so for x=9, the first value tested by loop is n=2, so 9 % 2 == 0 evaluates to false, so True is returned, the function ends. (the loop breaks in order for the function to end given a return keyword is reached)

Is this the behavior you want for your program? If not, what should we change?


#3

No, since I want the function to go through the full list of numbers in range(2, x-1). However, how would I do this without breaking on the first return statement?


#5

You know you’ve got a non-prime when you’ve found a divisor, and you know you’ve got a prime when you finished testing them all. <- this is rather self-evident, yet says everything about how to do it

Also, range(2, x-1) won’t include x-1, it’s rather weird to stop two numbers before x. The last one to test should probably be one less, or the largest number that, when squared, doesn’t exceed x


#6

well, the return keyword breaks the loop, so what should you do if you don’t want to break the loop?


#7

Place the for loop in an else statement after the if?


#8

Just write the loop and the condition and then ask yourself where in the code you’ll be when you’ve determined either result

Or for that matter, pick a few numbers and in your head test whether they are prime. Simply observe what you do and when you do it, you’re asking about where to stop, so consider when you stop.


#9

Oh, thanks! I finally got the answer :grinning:


#10

Extra takeaway

A prime number is not divisible by any primes that are less in value than its square root.

In other words, a range that exceeds this amount is pointless, but for the exercise, necessary to expose the heart of the lesson. Whether x-1 or x it is still moot. The only number that is divisibe by itself minus 1 is 2. This might hint as to why it is also a Prime.


#11

A prime number isn’t divisible

A number may be divisible by numbers larger than its square root, but the result will be lower than the square root and will therefore already have been tested

sqrt(10) -> ~3.16
10 is divisible 5 which is larger than 3.16


#12

Ah, so it should be the next Prime above of the square root that we can stop at?


#13

10 prime?

1 -> 10
2 -> 5
----------- passed sqrt(10), repeating, mirrored, no need to test the rest
5 -> 2
10 -> 1


#14

A point that has been on the radar. No prime is divisible by any prime that is less than its square root. A simple statement that while it comprises only a subset of test divisors, still proves true. Of course primes are not divisible. That is moot.

Narrowing down the divisor list should be a priority when doing iterative testing. If a number is not divisible by the sequence of primes in range that you throw at, it is prime, is it not?


#15

A prime isn’t divisible, the rest of the condition there is redundant. You might say something similar about a number, but it’ll still be divisible, and you’ll want to check the ones below the sqrt because that’s a much smaller range of numbers


#16

So we cannot rely exclusively upon prime factors?


15.6: is_prime
#17

That’s not what you’re saying though >.< and that would be a sieve, because you’d need to generate those primes

When doing trial division, stop where the pattern repeats itself, there is no more information to be found. It’ll repeat after the square root, because that’s where the the two factors are equally large (the turning point)

You’d either stop at x-1 (all numbers smaller than itself but greater than 1), or you’d stop before passing sqrt(x)
While x-2 turns out to be safe, it doesn’t help and is incredibly arbitrary and is only there because someone expected the range function to have an inclusive end bound, causing -1 to be applied twice for a total of -2

You’d make the code either match the definition, or you’d make a meaningful optimization and argue about why it’s correct. having the last number be -2 is neither of those


#18

Okay, so the original assertion still applies. 10 % 2 is zero so we never get to test if it is divisible by 5. 2 is less than 3.16…

D’uh moment. Relying on a sieve approach still entails building the sieve along the way, which may not be as efficient as brute force. Is this the point I’ve been missing all along?


#19

Why is the range (2, x-1)?
It should have been (2, x). Can anyone please explain?


#20

the instructions state we should use x-1, given we don’t want to include the value of x in the loop. However, range does not include the stop value. Unfortunately, many people fail to realize this so they give range a stop value of x-1

its still works of course, but its a fair point you make


#21

This particular peculiarity has been the subject of literally hundreds of similar questions and it speaks to the fact that the CC engineers never check for recurring discussions so minor errors like this could be fixed before they become a permanent pimple on the nose of the forums.