Re: Computing the 1000th prime
MRAB
> 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
>
The indentation starting from the second 'if'.
Benjamin Kaplan
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.
Benjamin Kaplan
> 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. >.<
Dave Angel
> 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:
> Thanks
>
>
There are a bunch of things wrong here. Did you write this code, or was
it copied from somewhere else? Because it looks like there are several
typos, that you could catch by inspection.
First, at what point in the loop do you decide that you have a prime?
Why not add a print there, printing the prime, instead of printing a
value that's already been incremented beyond it. And put labels on your
prints, or you'll never be able to decipher the output. Chnage the
limit for PrimeCount to something small while you're debugging, because
you can figure out small primes and composites by hand.
Second, you have a loop which divides by x. But you change the
PrimeCandidate within the loop, so it's not dividing the same value each
time through. Check your indentation.
Third, your limit value is too high. You aren't looking for 2000
primes, but 1000 of them. Further, your count is off by 1, as this loop
doesn't identify 2 as a prime.
I'd recommend making this whole thing a function, and have it actually
build and return a list of primes. Then the caller can check both the
size of the list and do a double check of the primality of each member.
And naturally you'll be able to more readily check it yourself, either
by eye or by comparing it to one of the standard list of primes you can
find on the internet.
The function should take a count, and loop until the len(primelist)
matches the count. Then just return the primelist.
DaveA