The Sieve of Eratosthenes

Eratosthenes was a Greek mathematician and astronomer. He served for a time as the head librarian in the famous Library at Alexandria. Among his scientific accomplishments was a measurement of the circumference of the earth that was accurate to within one percent. Our purpose here, however, is to look at a technique he invented to list all the prime numbers less than some given bound N.

The idea of the method is quite straightforward. You start by finding a large sheet of paper and inscribing on it all the numbers from 1 to N. Since the number 1 is not prime, cross it out. The smallest remaining number, 2 is prime. Leave it alone, and go through the entire list crossing out its multiples. Repeat this process, using the next smallest remaining number, 3. Continue processing this way until you have reached the end of the list. You will eventually cross out all the composite numbers and be left with a list of all the primes less than N.

Here is a table showing what happens when you apply this technique to the integers less than or equal to 100. Primes are shown in boldface, and composites are marked with a subscript indicating their smallest divisor.

Primes Less Than 100

11	2	3	42	5	62	7	82	93	102
11	122	13	142	153	162	17	182	19	202
213	222	23	242	255	262	273	282	29	302
31	322	333	342	355	362	37	382	393	402
41	422	43	442	453	462	47	482	497	502
513	522	53	542	555	562	573	582	59	602
61	622	633	642	655	662	67	682	693	702
71	722	73	742	753	762	777	782	79	802
813	822	83	842	855	862	873	882	89	902
917	922	933	942	955	962	97	982	993	1002

[Home Page] [Bioinformatics] [Mathematics] [Creative Efforts]

[HOME] [PREVIOUS] [NEXT] [UP] [DOWN]