### Sieve of Eratosthenes

The key fact that is used for the method discussed in this section is the fact that if is any composite than it must have a prime factor which is less than or equal to , by Lemma 1.2.5.

The method to produce all primes up to :

1. List all integers .
2. Let .
3. Cross out all multiples of except for itself.
4. If all integers between and are crossed out then stop. Otherwise, replace by then next largest integer which has not been crossed out. If this new is greater than then stop.
5. Go to step 3.

This process must terminate after at most steps.

Example 1.5.12   Let . step 1:

step 2: Cross out multiples of :

step 3: Cross out multiples of :

All the remaining numbers are prime.

Exercise 1.5.13   Using the Sieve of Eratosthenes, find all the primes from to .

Exercise 1.5.14   How many digits does have? (Hint: What is ?)

Exercise 1.5.15   Check that and are perfect.

Exercise 1.5.16   Determine the prime decomposition of (a) , (b) , (c) .

Exercise 1.5.17   Show that if is a prime, for some integer , then is also a prime.

Exercise 1.5.18   In the notation of §1.5.1, compute for

(a) , ,

(b) , ,

(c) , .

Exercise 1.5.19 (a)   Assume some encryption scheme requires a digit prime. It is unlikely you will find a such a prime on your first guess. Approximately how many digit integers would have to be randomly picked before a prime is found?

(b) Estimate how many 100-digit prime numbers there are.

Exercise 1.5.20   Assume is a real number greater than . Let

denote the Riemann zeta function. Here the sum runs over all integers . Let

denote the Euler product. Here the product runs over all prime numbers . Without worrying about convergence issues (using calculus, one can show that these series considered here all converge absolutely), show that . In other words, show

(Hint: Recall and use the Fundamental Theorem of Arithmetic.)

Exercise 1.5.21   Using the fundamental theorem of arithmetic, prove (1), (2), (3), and (4) of Proposition 1.2.16.

Exercise 1.5.22   Show that if is a prime then must also be a prime. (Hint: is divisible by .)

David Joyner 2007-09-03