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

Disclaimer: This page was last updated on 12 October 2002. It is entirely possible that the information contained herein no longer has any connection with reality (assuming it ever did). Feel free to send constructive comments or inane criticisms to:
Kevin R. Coombes
Department of Biostatistics
University of Texas M.D.Anderson Cancer Center
1515 Holcombe Blvd., Box 447
Houston, TX 77030