• 13
• 18
• 19
• 27
• 10

# Prime number program oddity

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

## 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 on other sites
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.