Python Forum - Finding prime numbers

Hi all,

So, this is a small thing that I know the answer to, but I'm just curious why the answer is what it is. I'm going through Codeacademy's python course, and right now it's having me create a little function that tests an inputted number to see if it's prime or not. I won't spoil the rest of the code, except to say that you have to say:

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

I don't understand why it's not range(2, x) instead of range(2, x-1). I mean, if you're testing 11, say, then it's going to test 11 % 2 through 11 % 10, because the stop point is up to but not including the stop point. In all cases, you're not going to have zero remainder, and given that it's also greater than 2, it's a prime number. I tested this in the exercise and it still ran without problems.

Any thoughts?

P.S.: I considering putting this under the homework sub-forum, but it's not homework, it's just something I'm doing out of curiosity.

Thanks!

Actually upper bound can be even lower. - x/2+1. Every number above that, multiplued by 2 will be greater than x, so pure math ligic suggest no need to test

Check ichabood's answer below for more details.

Actually, the upper bound is math.ceil(math.sqrt(x)). Any composite number will either be the square of a prime, or have a factor lower than it's square root to match any factor greater than it's square root.

(Jul-19-2018, 06:17 AM)ichabod801 Wrote: [ -> ]Actually, the upper bound is math.ceil(math.sqrt(x)). Any composite number will either be the square of a prime, or have a factor lower than it's square root to match any factor greater than it's square root.

Absolutely correct. That happens when you answer before drinking your morning coffee.

(Jul-19-2018, 06:22 AM)buran Wrote: [ -> ]That happens when you answer before drinking your morning coffee.

As opposed to being unable to sleep, in which case it's not late enough to be early yet.

So, you're saying the better code would be range(2, math.ceil(math.sqrt(x)))?

(Jul-20-2018, 12:49 AM)creslin_black Wrote: [ -> ]So, you're saying the better code would be range(2, math.ceil(math.sqrt(x)))?

Yes, but you have to import the math module first.

Isn't the full definition of a prime; a number that is only divisible by itself and 1? So isn't the original statement just checking that the number is divisible by 1?