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
