Newbie question - calculating prime numbers

[Ian]

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