Computing the 1000th prime

[Benjamin Kaplan]

On Thursday, November 12, 2009, Benjamin Kaplan
<benjamin.kaplan at case.edu> wrote:
> On Thursday, November 12, 2009, Ray Holt <mrholtsr at sbcglobal.net> wrote:
>>
>>
>>
>>
>>
>> I have an assigment
>> to find the 1000th. prime using python. What's wrong with the following
>> code:
>> PrimeCount =
>> 0
>> PrimeCandidate = 1
>> while PrimeCount < 2000:
>>
>> IsPrime = True
>>     PrimeCandidate = PrimeCandidate +
>> 2
>>     for x in range(2,
>> PrimeCandidate):
>>         if PrimeCandidate
>> % x ==
>> 0:
>> ##            print
>> PrimeCandidate, 'equals', x, '*',
>> PrimeCandidate/x
>>
>> print PrimeCandidate
>>
>>
>> IsPrime =
>> False
>>
>> break
>>         if
>> IsPrime:
>
> You break on the first composite number, which means you immediately
> exit the loop. Just let it fall through Also, a couple of things to
> speed in up:
>

Nevermind MRAB is right. I missed the indentation error there. I guess
that's what I get for  trying to evaluate code on my iPod touch
instead of getting my computer out and actually seeing what it's
doing.  >.<
> 1) you look at all numbers from 2 to n to check if n is a prime
> number. You only need to check from 2 to int(math.sqrt(n))
>
> 2) to really speed it up, keep a list of all the prime numbers. Then
> you only need to check if a number is divisible by those
>
> By combining the two, you'll only use a fraction of the comparisons.
> For 23, you'd only loop twice (2 and 3) instead of 20 times to
> determine that it's prime. The difference is even more dramatic on
> large numbers.
>