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: > > 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. -- http://mail.python.org/mailman/listinfo/python-list
