Jump to content
  • Advertisement
Sign in to follow this  
carlsonc

Prime number program oddity

This topic is 3087 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I decided to get a head start on college so I'm working through the MIT open courseware programming session. I figured out how to make the program work, but I don't understand why my previous trial is any different from the finished product. The object was to find the first 1000 primes, but the two codes give me different results that I didn't expect...I've run through the program in my head a few times and it just doesn't make sense to my why it would cause a problem.

INCORRECT VERSION
def primeGen():
testPrime = 1 #number being tested as a prime
primeNumber = 0 #number of primes
startNumber = 2 #incremental number

while primeNumber <= 1000: #stop after 1000 primes

while startNumber >= testPrime: #this will print 1 and 2
print testPrime #print out prime number
testPrime = testPrime + 1
primeNumber = primeNumber + 1
startNumber = 2 #reset the incremental number

while startNumber < testPrime:
if testPrime % startNumber == 0: #testing if prime or not
testPrime = testPrime + 1
#Here's where the missing segment that makes it work goes
else:
startNumber = startNumber + 1


CORRECT VERSION
def primeGen():
testPrime = 1 #number being tested as a prime
primeNumber = 0 #number of primes
startNumber = 2 #incremental number

while primeNumber <= 1000: #stop after 1000 primes

while startNumber >= testPrime: #this will print 1 and 2
print testPrime #print out prime number
testPrime = testPrime + 1
primeNumber = primeNumber + 1
startNumber = 2 #reset the incremental number

while startNumber < testPrime:
if testPrime % startNumber == 0: #testing if prime or not
testPrime = testPrime + 1
startNumber = 2 #why does adding this fix it?
else:
startNumber = startNumber + 1


The results should be the same as far as I figured...just a little confused.

The error results in only going to the 4000's instead of 7000's like it should.

Share this post


Link to post
Share on other sites
Advertisement
When testPrime % startNumber == 0, that means that startNumber is a divisor of testPrime, and thus, testPrime is not a prime number. So now you have to increment testPrime, but you also have to reset the startNumber (think of startNumber as your divisor).

Why do you have to reset it to 2? You have to reset startNumber back to 2 otherwise your startNumber will keep incrementing in the else: conditional even if it found a divisor.

As an example, imagine testPrime = 9. First startNumber will equal 2.

Does...
9 % 2 == 0? No
9 % 3 == 0? Yes

But now, you haven't reset startNumber to 2, so the next thing that will happen is this:

Does...
10 % 4 == 0?

You never checked if 2 or 3 mod 10 equals 0.

You might want to use a debugger and step through the code to watch what it is doing. For python, I tend to use Eclipse with the PyDev plugin.

Share this post


Link to post
Share on other sites
Ah ok, now I get why it would change it...I had it in my head that It would switch back to the first while loop where I already had it reset to 2. Thanks, I'll also go check out eclipse/pydev

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!