Newbie question - calculating prime numbers

[Matty Sarro]

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 <davea at 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100810/b65c6078/attachment-0001.html>