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.
[Home Page] [Bioinformatics] [Mathematics] [Creative Efforts]
[HOME] [PREVIOUS] [NEXT] [UP] [DOWN]