[Tutor] Spurious primes

[Danny Yoo]

On Wed, 30 Jan 2002, Sarney wrote:

> I'm attempting to 'think like a computer scientist'.  To this end, I set
> myself a trivial exercise of generating a list of primes.  I thought I had
> succeeded with the function below (after much gnashing of teeth & re-reading
> tutorials).  My pride was dashed when my I asked for 7 primes and got
> (2,3,5,7,11,13,16).


Let's take a look at the program.  After that, I'm going to bed.  *grin*


> a = [2]

Ah, ok, so whenever I see 'a', I'll think "the list of primes we've
found".  You might want to use a more descriptive name than 'a', since you
also use a few other one-letter variables.


> def test(x,a):
>    for i in a:
>       if x%i == 0:
>          x = x + 1
>          test(x,a)
>       else:
>          return x

Be careful --- if we want test() to return the very next prime that it
finds, we need to see that every possible twisty path will eventually
"return" a value.  In the code above, if 'x%i == 0' is true, test() does
does a recursive call, but it tosses away the result by not doing anything
with it.


Here's a version of test(x, a) that corrects that bug.  I've taken the
libery of renaming the variables, but you can change them back, of course.  
*grin*:

###
def findNextPrime(candidate, primes):
    for prime in primes:
        if candidate % prime == 0:
            candidate = candidate + 1
            return findNextPrime(candidate, primes)
        else:
            return candidate
###

There's still a bug in here --- see what happens when we do something
like:

    findNextPrime(9, [2,3,5,7])


Don't worry, you'll see it in time.  Good luck to you, and if you have
more questions, please ask them.