Newbie question - calculating prime numbers

Dave Angel davea at ieee.org
Tue Aug 10 14:51:47 CEST 2010


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




More information about the Python-list mailing list