Question

I just finished ps1a.py. Would you be so kind as to look it over and criticize it?

Answer 1

Here it is:

Answer 2

Well, you do get the right answer. Good job.

Answer 3

Well is it streamlined and efficient? Anything I can remove that isn't completely necessary or something I could change to make better?

Answer 4

Say I'm looking for whether 7919 is a prime number. Until when should I look? I believe you kept looking until 7919, but actually you only need to keep looking until the math.sqrt(7919). It's an existing theorem.

Answer 5

But how would I know what to take the square root of and search until without first computing the 1000th prime?

Answer 6

I don't think you understood. For every "check" in your program, only look for divisors until the square root of check. I changed 1 line in your code and it goes much faster :

added import math
for divisor in range(2,math.sqrt(check)+1)

Answer 7

You can cut that in half by only checking odds up to square root:
range(2,math.sqrt(check)+1,2)

Answer 8

Oops. I separated the two, that doesn't work for yours

Answer 9

GabeF's idea works as long as you precise that 2 IS indeed a prime number, since your loop won't look for it

Answer 10

oh ok i understand the square root thing now.

Answer 11

I removed corner cases, then check odds:

if num != int(num):
prime = False # non-integers are not prime
elif num < 2:
prime = False # 2 is the lowest prime
elif num%2 == 0:
prime = (num == 2) # The only even prime number is 2
else:
testAgainst = range(3,int(sqrt(num))+1,2) # No need to check even multiples
prime = True
for val in testAgainst:
if num%val == 0: # If any value divides the number evenly, it's not prime
prime = False
break

Answer 12

Well, there are a billion ways to do such a problem =p

For those that are interested, one of the best ways is called Sieve of Eratosthenes, though it is a little more complex

Answer 13

omg wow... before it took about 10 seconds now it does computes instantly x.x

Answer 14

No problemo. Become my fan xD

Answer 15

Do you have sample code solving this problem using Sieve of Eratothenes? I got it to work using the sieve, but it was slower. To find the 1000th prime, my code took 0.019 secs vs 1.367 secs using the sieve. Not asking to be a jerk...interested in whether or not I can reduce the calculation time (just for fun).

Answer 16

Ok for explanation sake lets say there is 10 books and you wanna divide them up for 3 people (which is 10books/3people) but for every person to have the same amount of books each person can only get 3 and then there will be one book that no one gets. The one no one gets would be considered the remainder. Also here is a link with a similar explanation but let me know if you need another explanation. http://www.homeschoolmath.net/teaching/md/not_exact_division.php

Answer 17

Oh my bad my computer keeps trippin out it posted this under wrong question

Answer 18

I'm not sure GabeF, you can probably Google a code. It is very popular.