1st Day Issue / Postalo Vleeptron: the Sieve of Eratosthenes

Click image, gets bigger.

First Day Issue: Postalo Vleeptron / the Sieve of Eratosthenes

An earlier Vleeptron image turned into a faux postage stamp.

Mainly because I love the Sieve of Eratosthenes so much. It was the first math thing that I found Truly Amazing.

At Alice Deal Junior High School in Washington DC a very long time ago, I was one of the Guinea Pigs for a new curriculum that came to be known as The New Math.

We learned about Sets (boring), and Sets of Numbers (boring), and finally about a set called the Prime Numbers.

They were sort of not boring.

A Prime Number is a whole number (Natural Number) which can only be divided evenly by itself and by 1.

The smallest Prime, and the only Even Prime, is 2.

The first few Primes are

2 ... 3 ... 5 ... 7 ... 11 ... 13 ... 17 ... 19 ... 23...

The teacher told us to find every Prime Number from 2 to 100.

Go ahead, get a pencil and paper and find all the Primes from 2 to 100.

DO NOT USE A COMPUTER OR CALCULATOR.

In junior high, pocket calculators hadn't been invented, and the only computers that existed were as big as an 18-wheel tractor-trailer, and belonged to huge corporations or secret agencies of the government.

I am lazy, and this was a lot of dull, repetitive hard work. I did not like this.

But I was impressed with how Irregular and Troublesome Prime Numbers were. They were like the Juvenile Delinquents or Non-Conformists of numbers. They were staring up from the paper and giving me the finger and mooning me and laughing at my discomfort and troubles. I was getting a cramp in my writing hand.

Then the teacher told us about the Sieve of Eratosthenes. He was the Librarian of the Great Library of Alexandria, Egypt.

Obviously he found Prime Numbers, and the laborious, tedious, repetitive work needed to find them, as annoying as I did.

So here's how his Sieve works.

A. Write all the numbers from 2 to 100 this way:

.....02...03...04...05...06...07...08...09...10
11...12...13...14...15...16...17...18...19...20
21...22...23...24...25...26...27...28...29...30
31...32...33...34...35...36...37...38...39...40
41...42...43...44...45...46...47...48...49...50
51...52...53...54...55...56...57...58...59...60
61...62...63...64...65...66...67...68...69...70
71...72...73...74...75...76...77...78...79...80
81...82...83...84...85...86...87...88...89...90
91...92...93...94...95...96...97...98...99..100

B. After 2, get rid of all the Even Numbers --.because they're all evenly divisible by 2.

.....02...03........05........07........09
11........13........15........17........19
21........23........25........27........29
31........33........35........37........39
41........43........45........47........49
51........53........55........57........59
61........63........65........67........69
71........73........75........77........79
81........83........85........87........89
91........93........95........97........99

C. The next number that hasn't been erased

...(in this case 3) is Prime. Keep it.

...After 3, erase every ODD MULTIPLE of 3:

09 ... 15 ... 21 ... 27 ... 33 ... 39 ...

.....02...03........05........07..........
11........13..................17........19
21........23........25..................29
31..................35........37..........
41........43..................47........49
..........53........55..................59
61..................65........67..........
71........73..................77........79
..........83........85..................89
91...../////........95........97

D. The next number that hasn't been erased is 5.

...Everything bigger that ends in the digit 5.is evenly divisible by 5, so get rid of it.

.....02...03........05........07..........
11........13..................17........19
21........23............................29
31............................37..........
41........43..................47........49
..........53............................59
61............................67..........
71........73..................77........79
..........83............................89
91............................97

E. If the next unerased number

...is greater than SQR(100) = 10

...Go To Step G.

F. Keep the next unerased number

...and erase every ODD MULTIPLE.

...Go To Step E.

G. Stop. All Done.

All the numbers that haven't been erased

are Prime -- all the Primes from 2 to 100.

Compare the Sieve with the first way you

tried to find all Primes from 2 to 100.

Those divisions (to see if Remainder = 0)

were horrible, and there were gazillions of them.

But the Sieve doesn't use divisions.

It only uses simple and very regular addition.

So it cuts through this block of whole numbers like a hot knife through butter.

Now ... what about all the Primes from 2 to 500 ?

Same as above, but

E. If the next unerased number
...is greater than SQR(500) = 22.4
...Go To Step G.

All Primes from 2 to 12,668 ?

E. If the next unerased number
...is greater than SQR(12,668) = 112.6
...Go To Step G.

Obviously we're getting beyond the range of Pencil and Paper.

But computers LOVE the Sieve. A computer can find all Primes

from 2 to 39,812,644,003 superquick and supereffortlessly!

Which is pretty strange, because Eratosthenes invented his Sieve about 22 centuries before anybody invented a high-speed digital computer.

If you can program, write 2 programs to make the computer find all Primes from 2 to 1,000,000 .

Program A does it with divisions

(or Modulo / MOD arithmetic,

which only computes the Remainder).

Program B does the Sieve.

Compare the run speeds.