- 3 Write Down The Numbers From 1 To 40 Starting With 2 2 Cross Out Every Second Number 4 6 8 10 Starting 1 (139.96 KiB) Viewed 13 times
3. Write down the numbers from 1 to 40. Starting with 2 2, cross out every second number: 4, 6, 8, 10, . . . . Starting with 2-3, cross out every third number: 6, 9, 12, 15, . . . . Starting with 2 - 5, cross out every fifth number: 10, 15, 20, . . . . Use the result of problem 1 to show that the numbers .. that are not crossed out (except for 1) are exactly the set of primes less than 40. 4. Generalize the result of problem 3 to show how you would find all primes less than or equal to a given integer n. Show that in using this method, it is not necessary to know the primes less than √n beforehand, since after the multiples of the jth prime have been crossed out, the next number remaining after the jth prime is the (j + 1)st prime. This method is known as the Sieve of Eratosthenes, and its generalizations have been used to construct the modern tables of primes. (For example, the 168 primes less than 1000 will produce all the primes less than 1 000 000.)