On Thursday, November 12, 2009, Ray Holt <mrhol...@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
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.kap...@case.edu> wrote: > On Thursday, November 12, 2009, Ray Holt <mrhol...@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.
Ray Holt 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
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.
|
