Prev: shelf-like list?
Next: type enforcement in _ssl.sslwrap
From: Dave Angel on 10 Aug 2010 08:51
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

From: Ian on 10 Aug 2010 09:14
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

From: Peter Otten on 10 Aug 2010 09:18
Matty Sarro wrote:

> 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))

Congrats!

One obvious thing would be to replace the "true" and "false" strings with
actual boolean values:

isPrime = True
....
while isPrime and i <= halfCand:
...

etc.

For a different perspective on the problem have a look at

http://mail.python.org/pipermail/python-list/2009-November/1226626.html

Peter

From: Dave Angel on 10 Aug 2010 09:50
Matty Sarro wrote:
> 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))
>
> <snip>
You top-posted, which messed up the message sequence. You should post
your message AFTER whatever you're quoting.

Your code starts by printing that 1 is prime, which it's not. And it
doesn't print 2. Those two errors happen to cancel, so the 1000th prime
is still right. But the initial value for candidate= should be 3, not
1. I didn't try to figure where the other error is, but somewhere your
count is off by one.

You've changed your code from using the built-in control flow to doing
it by hand. That's almost never a good idea, and in this case it'll
slow you down. Learn about the break statement to break out of a for
loop or while loop. It saves doing multiple tests in the loop construct.

Use True and False, not strings.

Your halfCand could have been rootCand; you only need to check up to
the square root of the candidate (see math.sqrt()). In fact, you only
need to check those primes you've already built, up to the square root.
For example, to tell if 23 is prime, you only need to divide by 2, 3 and
5. This would require that you build a list of results, appending to it
whenever you find a new prime. It would mean that primeCount is not
needed, as it's simply len(primeList).

I don't know which of these ideas has already been covered in your
class. But if you used all of these ideas, your code would be smaller
and much faster.

Currently, it spends more time in the print statements than in
calculating, so I temporarily commented out the print of the first 999
primes.

I coded up a quick version, and without the prints of individual primes,
it sped up 1.3 secs to 0.03 secs.
If I have both versions do the first 10,000 primes, the original takes
176 secs, while mine takes 0.5

DaveA

 | 
Pages: 1
Prev: shelf-like list?
Next: type enforcement in _ssl.sslwrap