On Thursday, November 12, 2009, Benjamin Kaplan <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. > -- http://mail.python.org/mailman/listinfo/python-list
