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.

1_{1} | 2 | 3 |
4_{2} | 5 | 6_{2} |
7 | 8_{2} | 9_{3} |
10_{2} |

11 | 12_{2} | 13 |
14_{2} | 15_{3} |
16_{2} | 17 | 18_{2} |
19 | 20_{2} |

21_{3} | 22_{2} | 23 |
24_{2} | 25_{5} |
26_{2} | 27_{3} |
28_{2} | 29 | 30_{2} |

31 | 32_{2} | 33_{3} | 34_{2} | 35_{5} |
36_{2} | 37 | 38_{2} |
39_{3} | 40_{2} |

41 | 42_{2} | 43 |
44_{2} | 45_{3} |
46_{2} | 47 | 48_{2} |
49_{7} | 50_{2} |

51_{3} | 52_{2} | 53 |
54_{2} | 55_{5} |
56_{2} | 57_{3} |
58_{2} | 59 | 60_{2} |

61 | 62_{2} | 63_{3} |
64_{2} | 65_{5} |
66_{2} | 67 | 68_{2} |
69_{3} | 70_{2} |

71 | 72_{2} | 73 |
74_{2} | 75_{3} |
76_{2} | 77_{7} |
78_{2} | 79 | 80_{2} |

81_{3} | 82_{2} | 83 |
84_{2} | 85_{5} |
86_{2} | 87_{3} |
88_{2} | 89 | 90_{2} |

91_{7} | 92_{2} | 93_{3} |
94_{2} | 95_{5} |
96_{2} | 97 | 98_{2} |
99_{3} | 100_{2} |

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

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

Kevin R. Coombes

Department of Biostatistics

University of Texas M.D.Anderson Cancer Center

1515 Holcombe Blvd., Box 447

Houston, TX 77030