Sieve of Eratosthenes

The sieve of Eratosthenes is an easy to use algorithm for finding all prime numbers up to a certain limit. It is named after Eratosthenes of Cyrene, a Greek mathematician who lived in third century BC. In this post we illustrate the sieve of Eratosthenes in a series of diagrams.

The sieve identifies the prime numbers below a limit n by eliminating all composite numbers below n. The following describes the steps:

  • Start with a listing of all positive integers \le n.
  • \text{ }

  • Select the number 2 and mark all multiples of 2 that are greater than 2 (in the diagrams below we use shading), essentially marking all even integers in the listing (except for 2).
  • \text{ }

  • In each subsequent step, find the first number p greater than the previously selected number. Then mark all multiples of p that are greater than p, i.e., marking 2p, 3p, 4p, \cdots.
  • \text{ }

  • The process is stopped when multiples of x have been marked for all integers x \le \sqrt{n}.

The justification for \sqrt{n} in the above description is that any composite integer in the listing would have a prime divisor below \sqrt{n}. See the corollary at the end of the post.

The sieve of Eratosthenes is of course best done using using computer. We illustrate the process by finding all prime number below n=169.

___________________________________________________________________________________________________________________

We start with Figure 1 which is a listing of all integers below 169.

Figure 1 – Positive Integers Below 169

Next, in Figure 2, we shade all multiples of 2 that are above 2. In other words we shade all even integers below 169 (excluding 2).

Figure 2 – Multiples of 2 are Shaded

The first number greater than 2 that has not been shaded is 3. In Figure 3 below, we shade all multiples of 3 that are greater than 3 and that have not been previously shaded (e.g. 9, 15, etc).

Figure 3 – Multiples of 3 are Shaded

The first number greater than 3 that has not been shaded is 5. In Figure 4 below, we shade all multiples of 5 that are greater than 5 and that have not been previously shaded.

Figure 4 – Multiples of 5 are Shaded

The first number greater than 5 that has not been shaded is 7. In Figure 5 below, we shade all multiples of 7 that are greater than 7 and that have not been previously shaded (e.g. 49, 77, 91, etc).

Figure 5 – Multiples of 7 are Shaded

The first number greater than 7 that has not been shaded is 11. In Figure 6 below, we shade all multiples of 11 that are greater than 11 and that have not been previously shaded. In this step, we only need to shade 121 and 143.

Figure 6 – Multiples of 11 are Shaded

The first number greater than 11 that has not been shaded is 13. In Figure 7 below, we shade all multiples of 13 that are greater than 13 and that have not been previously shaded. In this step, we only need to shade 169.

Figure 7 – Multiples of 13 are Shaded

By the time we finish with Figure 7, all multiples of x have been shaded for all x \le 13=\sqrt{169}. So the remaining unshaded numbers are prime numbers. Note that for any integer in the above diagrams, if it is composite, it would have a prime divisor at or below 13 (see the corollary below).

Thus there are 39 prime numbers below 169 and they are:

    2, 3, 5, 7,

    11, 13, 17, 19,

    23, 29,

    31, 37,

    41, 43, 47,

    53, 59,

    61, 67,

    71, 73, 79,

    83, 89,

    97,

    101, 103, 107, 109,

    113,

    127,

    131, 137, 139,

    149,

    151, 157,

    163, 167

___________________________________________________________________________________________________________________

Why the Sieve Works

The marking or shading of multiples of numbers can stop at \sqrt{n} is justified by the following two lemmas.

Lemma 1
Let n be a composite integer greater than 1. Then n has a divisor d such that 1<d \le \sqrt{n}.

Proof.
Since n is composite, there are integers d and h such that n=d \cdot h with 1<d<n and 1<h<n. If one of d and h is \le \sqrt{n}, then we are done.

Suppose that both d>\sqrt{n} and h>\sqrt{n}. Then we have:

    n=d \cdot h>\sqrt{n} \cdot \sqrt{n}=n

Thus one of d and h is \le \sqrt{n}. \blacksquare

Lemma 2
Let n be a composite integer greater than 1. Then n has a prime divisor d such that 1<d \le \sqrt{n}.

Proof.
By Lemma 1, n has a divisor d such that 1<d \le \sqrt{n}. Since there can be only finitely many such divisors and since any finite set of real numbers has a least element, let d be the smallest divisor of n such that 1<d \le \sqrt{n}. Then d must be a prime number. If not, by Lemma 1 d would have a divisor w with 1<w \le \sqrt{d}<d. This would mean w is a divisor of n contradicting the fact that d is the smallest divisor of n. \blacksquare

Because of these two lemmas, in checking whether a positive integer is a prime number, we only need to check for divisors \le \sqrt{n}. We have the following corollary, which is the basis of the sieve of Eratosthenes.

Corollary
Let n be any integer greater than 2. Any composite number k in the following listing

    \left\{2,3,4,5,6, \cdots, n-1,n \right\}

has a prime factor p \le \sqrt{n}.

Thus in the process for the sieve of Eratosthenes for identifying the prime numbers \le n, we only need to eliminate the multiples of p for all p \le \sqrt{n}.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s