Re: Newbie question - calculating prime numbers
Matty Sarro wrote: Hey Everyone, I'm currently trying to work through MIT's opencourseware and am using python. The second assignment they offer is to determine the 1000th prime number. Below is the code I am using: #Assignment 1a #Determine the 1000th prime number candidate=3 #Already know that 2 is prime primeCount=1 while (primeCount=1000): for i in range (2,candidate): if ((candidate%i)==0): print(candidate, is not a prime) else: print(candidate, is a prime!) primeCount+=1 candidate+=2 Now I'm not looking for a solution, but I'm hoping that someone can at least tell me where the error in my logic is. The outer loop keeps count and will keep iterating until the 1000th prime number has been found. The inner loop just attempts to divide the candidate number by each possible factor until it's reached, and then increases the candidate number value by two since even numbers above 2 aren't prime. The if statement inside the inner loop simply checks if there is a remainder when attempting to divide the candidate by the possible factor. If there isn't, its a factor and we can print not a prime. If there is always a remainder, nothing is a factor and so the candidate is a prime. I figured it seemed simple enough, but I keep getting a massive output and almost nothing listed is a correct prime number. Please be gentle, its my first post and I haven't programmed in ages :) -Matty Once you discover a particular value is not a prime, you need to get out of that for loop. Add a break after the appropriate print. Also, the print that says it IS a prime is misplaced. You only know that if you've gone all the way through the loop without ever hitting the break. That's a candidate for the 'else' clause of the for loop. There are other changes you could make for efficiency, but get it working correctly first. DaveA -- http://mail.python.org/mailman/listinfo/python-list
Re: Newbie question - calculating prime numbers
Hey Dave, Thank you for the heads up. I actually bashed my head against the desk a few times and eventually I realized what I was doing wrong. Here's my final code (slightly optimized) that's verified and working. Out of curiousity, what other optimizations could I throw at it (without diving too deep too fast). #Assignment 1a #Determine the 1000th prime number candidate=1 #Already know that 2 is prime primeCount=1 while (primeCount=1000): isPrime=true i=2 halfCand=(candidate/2) while (isPrime==true) and (i=halfCand): if ((candidate%i)==0): isPrime=false else: i+=1 if isPrime==true: print(candidate, is a prime.) primeCount+=1 #else: #print(candidate, is not a prime.) candidate+=2 print(The 1000th prime number is ,(candidate-2)) On Tue, Aug 10, 2010 at 8:51 AM, Dave Angel da...@ieee.org wrote: Matty Sarro wrote: Hey Everyone, I'm currently trying to work through MIT's opencourseware and am using python. The second assignment they offer is to determine the 1000th prime number. Below is the code I am using: #Assignment 1a #Determine the 1000th prime number candidate=3 #Already know that 2 is prime primeCount=1 while (primeCount=1000): for i in range (2,candidate): if ((candidate%i)==0): print(candidate, is not a prime) else: print(candidate, is a prime!) primeCount+=1 candidate+=2 Now I'm not looking for a solution, but I'm hoping that someone can at least tell me where the error in my logic is. The outer loop keeps count and will keep iterating until the 1000th prime number has been found. The inner loop just attempts to divide the candidate number by each possible factor until it's reached, and then increases the candidate number value by two since even numbers above 2 aren't prime. The if statement inside the inner loop simply checks if there is a remainder when attempting to divide the candidate by the possible factor. If there isn't, its a factor and we can print not a prime. If there is always a remainder, nothing is a factor and so the candidate is a prime. I figured it seemed simple enough, but I keep getting a massive output and almost nothing listed is a correct prime number. Please be gentle, its my first post and I haven't programmed in ages :) -Matty Once you discover a particular value is not a prime, you need to get out of that for loop. Add a break after the appropriate print. Also, the print that says it IS a prime is misplaced. You only know that if you've gone all the way through the loop without ever hitting the break. That's a candidate for the 'else' clause of the for loop. There are other changes you could make for efficiency, but get it working correctly first. DaveA -- http://mail.python.org/mailman/listinfo/python-list
Re: Newbie question - calculating prime numbers
On 10/08/2010 12:57, Matty Sarro wrote: Hey Everyone, I'm currently trying to work through MIT's opencourseware and am using python. The second assignment they offer is to determine the 1000th prime number. Below is the code I am using: #Assignment 1a #Determine the 1000th prime number candidate=3 #Already know that 2 is prime primeCount=1 while (primeCount=1000): for i in range (2,candidate): if ((candidate%i)==0): print(candidate, is not a prime) else: print(candidate, is a prime!) primeCount+=1 candidate+=2 Now I'm not looking for a solution, but I'm hoping that someone can at least tell me where the error in my logic is. Hi Matty, Dave Angel has already given you some helpful stuff. I would only like to add that you need three states inside your loop a) Candidate is known to be prime b) Candidate is known to be not prime c) Candidate may or may not be prime and the code has to keep working on it. You are detecting the is not prime case correctly. The other two situations are confused. A candidate is only prime if it is not divisible by *any* number other than 1 or itself. Two hints for efficiency: If candidate has a factor, one of those factors MUST be = square root of candidate - so you don't need to loop through so many. If x is prime, all multiples of x are not prime. See sieve of Eratosthenes. Regards Ian -- http://mail.python.org/mailman/listinfo/python-list
Re: Newbie question - calculating prime numbers
Matty Sarro wrote: Hey Dave, Thank you for the heads up. I actually bashed my head against the desk a few times and eventually I realized what I was doing wrong. Here's my final code (slightly optimized) that's verified and working. Out of curiousity, what other optimizations could I throw at it (without diving too deep too fast). #Assignment 1a #Determine the 1000th prime number candidate=1 #Already know that 2 is prime primeCount=1 while (primeCount=1000): isPrime=true i=2 halfCand=(candidate/2) while (isPrime==true) and (i=halfCand): if ((candidate%i)==0): isPrime=false else: i+=1 if isPrime==true: print(candidate, is a prime.) primeCount+=1 #else: #print(candidate, is not a prime.) candidate+=2 print(The 1000th prime number is ,(candidate-2)) Congrats! One obvious thing would be to replace the true and false strings with actual boolean values: isPrime = True ... while isPrime and i = halfCand: ... etc. For a different perspective on the problem have a look at http://mail.python.org/pipermail/python-list/2009-November/1226626.html Peter -- http://mail.python.org/mailman/listinfo/python-list
Re: Newbie question - calculating prime numbers
Matty Sarro wrote: Hey Dave, Thank you for the heads up. I actually bashed my head against the desk a few times and eventually I realized what I was doing wrong. Here's my final code (slightly optimized) that's verified and working. Out of curiousity, what other optimizations could I throw at it (without diving too deep too fast). #Assignment 1a #Determine the 1000th prime number candidate=1 #Already know that 2 is prime primeCount=1 while (primeCount=1000): isPrime=true i=2 halfCand=(candidate/2) while (isPrime==true) and (i=halfCand): if ((candidate%i)==0): isPrime=false else: i+=1 if isPrime==true: print(candidate, is a prime.) primeCount+=1 #else: #print(candidate, is not a prime.) candidate+=2 print(The 1000th prime number is ,(candidate-2)) snip You top-posted, which messed up the message sequence. You should post your message AFTER whatever you're quoting. Your code starts by printing that 1 is prime, which it's not. And it doesn't print 2. Those two errors happen to cancel, so the 1000th prime is still right. But the initial value for candidate= should be 3, not 1. I didn't try to figure where the other error is, but somewhere your count is off by one. You've changed your code from using the built-in control flow to doing it by hand. That's almost never a good idea, and in this case it'll slow you down. Learn about the break statement to break out of a for loop or while loop. It saves doing multiple tests in the loop construct. Use True and False, not strings. Your halfCand could have been rootCand; you only need to check up to the square root of the candidate (see math.sqrt()). In fact, you only need to check those primes you've already built, up to the square root. For example, to tell if 23 is prime, you only need to divide by 2, 3 and 5. This would require that you build a list of results, appending to it whenever you find a new prime. It would mean that primeCount is not needed, as it's simply len(primeList). I don't know which of these ideas has already been covered in your class. But if you used all of these ideas, your code would be smaller and much faster. Currently, it spends more time in the print statements than in calculating, so I temporarily commented out the print of the first 999 primes. I coded up a quick version, and without the prints of individual primes, it sped up 1.3 secs to 0.03 secs. If I have both versions do the first 10,000 primes, the original takes 176 secs, while mine takes 0.5 DaveA -- http://mail.python.org/mailman/listinfo/python-list
