Eratosthenes

Eratosthenes (276–194 B.C.) was a Greek mathematician and astronomer who was a contemporary of Archimedes and Appolonius. He wrote many books and was the director of the Library of Alexandria.

One of Eratosthenes' nicknames was "Pentathlos", implying that he was a polymath. He wrote treatises on history, theatre, ethics, and geography. However, he is remembered for the two following discoveries: His accurate measurement of the circumference of the earth, and his method for determining prime numbers.

The Circumference of the Earth

While the idea that the Earth is round was not uncommon among ancient Greek philosophers, Eratosthenes was able to demonstrate this fact, and calculate the Earth's circumference accurately. The ancients noticed that, in the city of Syene (modern day Aswan), at noon on June 21, the sun is directly overhead. Shadows of vertical columns and sticks disappeared. A shaft of sunlight penetrated to the bottom of a well. This fact aroused Eratosthenes' curiosity, and he did an experiment to determine whether vertical sticks cast shadows in Alexandria at noon on the summer solstice. As it turned out, they do.

This result can't be explained if the Earth is flat. If a stick doesn't cast a shadow in one point, then it wouldn't at another point. The conclusion that Eratosthenes drew is that the surface of the Earth had to be curved. For the observed difference in shadow lengths, Eratosthenes calculated that the distance between Alexandria and Syene had to be ¹/₅₀^th of a circle with its centre at the centre of the Earth. In other words, the sun was about seven degrees south of the zenith at Alexandria when it was directly overhead at Syene. Eratosthenes also knew that the distance between Alexandria and Syene was 4,800 stadia (in modern units, the distance is about 800 kilometres or 500 miles), because he hired a man to pace the distance(!). 5,000 stadia times 50 is 250,000 stadia (this would work out to about 40,000 kilometres). Eratosthenes later fine-tuned this result to 252,000 stadia. This must be the circumference of the Earth. This is correct with an error of only a few percent, a remarkable achievement for ancient times. This makes Eratosthenes the first person to accurately determine a planet's size.

The Sieve of Eratosthenes

Eratosthenes also devised one of the earliest methods for finding prime numbers. He created a numerical sieve that would eliminate composite numbers up to some given number. Let's take a look at how it works.

First, determine the maximum number you want to work with (here, 100). Write the numbers down in a table.

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	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

Find the first prime in the list, which is 2. Circle it and cross off all of the multiples of two in the table. (And yes, that "4" is crossed out. I've found that it's hard to tell with some browsers.)

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	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

Find the next prime, 3, and cross off all the multiples of 3.

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	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

Do the same thing for 5...

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	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

And 7...

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	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

...and repeat the process for all of the primes that are less than or equal to the square root of the largest number in the table (see also shortcuts for testing for divisibility). In this example, the largest number is 100, whose square root is 10. The only primes smaller than 10 are 2, 3, 5, and 7, so we're done. At least one of the factors of a composite number must be less than or equal to the square root of that number; If you think about it for a bit, you can see why.

All of the numbers which are not crossed off (with the exception of 1, which is neither prime nor composite) are prime numbers. This method works like a sieve, letting the composite numbers sift through while keeping the prime numbers. In general, the Sieve of Eratosthenes can catch all prime numbers below any given number.