In this exercise you will use an algorithm, called the sieve of Eratosthenes,
that isolates prime numbers. (Eratosthenes lived from about 276 to 194
b.c. He was also known for his computation of the circumference of the
earth and for his treatises on the theater, moral philosophy, and history.)
Here is how it works. List the integers from 2 through n. Circle the
number 2, then cross off all the higher multiples of 2 (namely, 4, 6, 8,
10, etc.). Circle 3, which is the first remaining number after 2. Then
cross off all the multiples of 3 that have not yet been crossed off. Then
circle 5. Et cetera. When you are finished with the repeated sieving
operations, only the primes will remain on the list, and they will have been
circled for emphasis. The exercise: perform the sieve of Eratosthenes with
n = 120. As you do this, cross off the multiples of different primes by using
different kinds of slashes (slashing in different directions, or using different
colors), and provide a key for the reader. By this device the reader will
immediately know the smallest prime divisor of each composite number
on your list. (In view of Exercise 4, after the multiples of 7 have been
crossed off, the remaining numbers will all be prime and can be circled to
mark this fact.)
In this exercise you will use an algorithm, called the sieve of Eratosthenes,
that isolates prime numbers. (Eratosthenes lived from about 276 to 194
b.c. He was also known for his computation of the circumference of the
earth and for his treatises on the theater, moral philosophy, and history.)
Here is how it works. List the integers from 2 through n. Circle the
number 2, then cross off all the higher multiples of 2 (namely, 4, 6, 8,
10, etc.). Circle 3, which is the first remaining number after 2. Then
cross off all the multiples of 3 that have not yet been crossed off. Then
circle 5. Et cetera. When you are finished with the repeated sieving
operations, only the primes will remain on the list, and they will have been
circled for emphasis. The exercise: perform the sieve of Eratosthenes with
n = 120. As you do this, cross off the multiples of different primes by using
different kinds of slashes (slashing in different directions, or using different
colors), and provide a key for the reader. By this device the reader will
immediately know the smallest prime divisor of each composite number
on your list. (In view of Exercise 4, after the multiples of 7 have been
crossed off, the remaining numbers will all be prime and can be circled to
mark this fact.)
