Computing the 1000th prime

[Benjamin Kaplan]

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:
>
> PrimeCount = PrimeCount +
> 1
>
> PrimeCandidate = PrimeCandidate +
> 2
>         print
> PrimeCandidate
> Thanks
>

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:

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.