Matty Sarro wrote:
Hey Dave,
Thank you for the heads up. I actually bashed my head against the desk a few
times and eventually I realized what I was doing wrong. Here's my final code
(slightly optimized) that's verified and working. Out of curiousity, what
other optimizations could I throw at it (without diving too deep too fast).
#Assignment 1a
#Determine the 1000th prime number
candidate=1
#Already know that 2 is prime
primeCount=1
while (primeCount<=1000):
isPrime="true"
i=2
halfCand=(candidate/2)
while (isPrime=="true") and (i<=halfCand):
if ((candidate%i)==0):
isPrime="false"
else:
i+=1
if isPrime=="true":
print(candidate, "is a prime.")
primeCount+=1
#else:
#print(candidate, " is not a prime.")
candidate+=2
print("The 1000th prime number is ",(candidate-2))
<snip>
You top-posted, which messed up the message sequence. You should post
your message AFTER whatever you're quoting.
Your code starts by printing that 1 is prime, which it's not. And it
doesn't print 2. Those two errors happen to cancel, so the 1000th prime
is still right. But the initial value for candidate= should be 3, not
1. I didn't try to figure where the other error is, but somewhere your
count is off by one.
You've changed your code from using the built-in control flow to doing
it by hand. That's almost never a good idea, and in this case it'll
slow you down. Learn about the break statement to break out of a for
loop or while loop. It saves doing multiple tests in the loop construct.
Use True and False, not strings.
Your halfCand could have been rootCand; you only need to check up to
the square root of the candidate (see math.sqrt()). In fact, you only
need to check those primes you've already built, up to the square root.
For example, to tell if 23 is prime, you only need to divide by 2, 3 and
5. This would require that you build a list of results, appending to it
whenever you find a new prime. It would mean that primeCount is not
needed, as it's simply len(primeList).
I don't know which of these ideas has already been covered in your
class. But if you used all of these ideas, your code would be smaller
and much faster.
Currently, it spends more time in the print statements than in
calculating, so I temporarily commented out the print of the first 999
primes.
I coded up a quick version, and without the prints of individual primes,
it sped up 1.3 secs to 0.03 secs.
If I have both versions do the first 10,000 primes, the original takes
176 secs, while mine takes 0.5
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
