Re: prime numbers and African artifact

Nick Barnes (nickb@harlequin.co.uk)
Wed, 12 Jul 1995 12:11:56 GMT

In article <rfJ0meEYsDj7075yn@fox.nstn.ns.ca> doldridg@fox.nstn.ns.ca
(Dave Oldridge) succumbs to a troll and attempts to describe the sieve
of Eratosthenes:

There's an easy procedure for producing the series--one that can even be
implemented with pebbles. You lay out a whole lot of pebbles in a row.
Then, starting with the 2nd pebble, you remove every 2nd pebble. After
that, you start with the third pebble and remove every 3rd pebble. Next
you go to the 5th pebble (you already removed the 4th) and remove every
5th pebble...and so on until you've removed all you can.

Of course, as described this will not leave you with the prime
pebbles.

start:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

start at the second pebble and remove every 2nd pebble:

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53

start at the 3rd pebble and remove every 3rd pebble (watch carefully):

1 3 7 9 13 15 19 21 25 27 31 33 37 39 43 45 49 51 55 57 61 63 67 69 73 75

start at the, erm, 7th pebble and remove every 7th pebble:

1 3 7 9 13 15 21 25 27 31 33 37 43 45 49 51 55 57 63 67 69 73 75

etc, leaving you with this:

1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75

Nick Barnes, speaking for himself (around my tongue)