 |
| Eratosthenes |
Tonight I have been thinking about applications of the principle of inclusion-exclusion. The gist of it is how to determine how many elements are in the union of two finite sets. Ideally, you want to determine that number without examining every element. That is done by figuring out which elements need to be examined (the inclusion part) and which elements can be ignored (the exclusion part).
A wonderful example of applying the principle of inclusion-exclusion is "The Sieve of Eratosthenes" which is used to find all primes not exceeding a specified positive integer. At this point you might be thinking this is just an application of divide-and-conquer, and I agree. Simple concepts can be very powerful.
Consider that Eratosthenes lived between 276 and 194 B.C.E. He was born in Cyrene, a Greek colony west of Egypt. Eratosthenes tutored the son of King Ptolemy II and was the chief librarian at the famous library at Alexandria. His amazing feats of intellect includes measuring the size of the Earth. Carl Sagan mentions Eratosthenes in the 1980 mini series, Cosmos. He explains how Eratosthenes measured the Earth and it is amazing to think that with our modern tools a family can use these same methods to not only repeat the experiment but to prove that the Earth is [mostly] round as well.
