Newbie question - calculating prime numbers
Ian
hobson42 at gmaiil.com
Tue Aug 10 15:14:27 CEST 2010
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
More information about the Python-list
mailing list