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 :

- List all integers .
- Let .
- Cross out all multiples of except for itself.
- 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.
- 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.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