Newbie question - calculating prime numbers

[Dave Angel]

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