[Tutor] Spurious primes

[Remco Gerlich]

On  0, Sarney <sarney@bigpond.com> wrote:
> Dear list members,
> 
> 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).  After some more testing, I realised it was spitting out
> these spurious primes after testing a number with more than one factor in
> the list 'a' (e.g 15 & 21).
> 
> Where have I gone wrong?
> 
> Regards, Robert
> ________________________
> 
> a = [2]
> 
> def test(x,a):
>    for i in a:
>       if x%i == 0:
>          x = x + 1
>          test(x,a)
> 
>       else:
>          return x

The problem is here. Say, you test 15, the list of primes so far is
[2,3,5,7,11,13]. 15 is not divisable by 2, but it is divisable by 3.

Now what happens? x is increased, so we start testing 16. Also, test(16,a)
is a called again - but its result is thrown away, so that call does nothing!

Now the bug: we're still counting i, so 16 won't be tested against 2 and 3,
but the first test is if it's divisable by 5.


> num = int(raw_input("how many primes do you want? "))
> 
> while len(a) <= num - 1:
>    a.append(test(a[-1]+1,a))
> 
> 
> print a

You're making it too complicated by making a function that tests if the
number is prime, *and* tries to find the next prime in case it isn't. Do
just one thing.

If you turn test(x, a) into a function that returns 1 if the number is prime and 0
if it isn't, you can change the loop into

x = 3
a = [2]

while len(a) < num:
   if test(x, a):
      a.append(x)
   x += 1

I think you can write the test function yourself.

Also - please use better variable names. Often just chosing a good variable
name makes it obvious that a function or variable is trying to be two things
instead of one. Like "candidate" and "primelist" for x and a would make the
code clearer already.

There are more efficient ways to get primes - for instance, to get all the
primes between 2 and n, start with range(2,n+1). Then repeat: 
  1.The first number is prime, add it to primelist 
  2.Delete all multiples of this number rom the list. 
This is called the Sieve of Eratosthenes.

-- 
Remco Gerlich