[Tutor] Spurious primes
Remco Gerlich
scarblac@pino.selwerd.nl
Wed, 30 Jan 2002 12:06:53 +0100
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