Python Forum
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Finding prime numbers
#1
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!
Reply
#2
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.
If you can't explain it to a six year old, you don't understand it yourself, Albert Einstein
How to Ask Questions The Smart Way: link and another link
Create MCV example
Debug small programs

Reply
#3
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.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#4
(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.

Doh Wall Absolutely correct. That happens when you answer before drinking your morning coffee.
If you can't explain it to a six year old, you don't understand it yourself, Albert Einstein
How to Ask Questions The Smart Way: link and another link
Create MCV example
Debug small programs

Reply
#5
(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.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#6
So, you're saying the better code would be range(2, math.ceil(math.sqrt(x)))?
Reply
#7
(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.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#8
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?
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  prime numbers with iterator and generator cametan_001 8 1,771 Dec-17-2022, 02:41 PM
Last Post: cametan_001
  prime numbers astral_travel 28 3,472 Nov-08-2022, 09:23 PM
Last Post: astral_travel
  Finding line numbers starting with certain string Sutsro 3 2,481 Jun-27-2020, 12:36 PM
Last Post: Yoriz
  Return prime numbers from range krzyfigh 2 1,885 Apr-20-2020, 08:08 PM
Last Post: krzyfigh
  Prime numbers Anderi02 1 1,941 Oct-13-2019, 04:49 PM
Last Post: ichabod801
  first k non-prime numbers arycloud 11 7,131 Jul-09-2019, 02:19 PM
Last Post: abhi19935
  first k non prime numbers print bsrohith 7 7,421 Jun-20-2019, 10:48 AM
Last Post: arycloud
  Print Numbers starting at 1 vertically with separator for output numbers Pleiades 3 3,662 May-09-2019, 12:19 PM
Last Post: Pleiades
  Finding perfect numbers BillMcEnaney 6 4,300 Apr-04-2019, 04:46 AM
Last Post: BillMcEnaney
  Prime Numbers OmarSinno 1 4,351 Sep-23-2017, 05:29 PM
Last Post: ichabod801

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020