Sieve of Eratosthenes | Research & Encyclopedia Articles

Sieve of Eratosthenes

The sieve of Eratosthenes is a useful method for making a list of prime numbers. Let d and n be positive integers. We say that d divides n, or that d is a divisor of n, if the fraction n/d is an integer. For example, 4 divides 12 and 1 divides 17, but 3 does not divide 14. The set of divisors of 12 is {1, 2, 3, 4, 6, 12}, and the set of divisors of 17 is {1, 17}. Sometimes it is important to include negative integers in a discussion of divisors. But in this article we will consider only positive integers and positive divisors. A positive integer n > 1 is called a prime number if the only divisors of n are 1 and n. A positive integer n >1 is said to be a composite number if it is not prime. The sequence of prime numbers begins with 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,.... Prime numbers are important in number theory because every positive integer n > 1 can be written as a product of prime numbers. For example,

(2)(2)(5)(5) = 100 and (7)(7)(11)(181619) = 97892641.

In fact each positive integer n > 1 can be written as a product of prime numbers in essentially one way. Here is a more precise statement of this fact: suppose that n > 1 is a positive integer, p₁, p₂, p₃,...,p_M is a collection of prime numbers arranged so that

p₁ p₂ p₃ ... p_M,

and q₁, q₂, q₃,...,q_N is a collection of prime numbers arranged so that

q₁ q₂ q₃ ... q_N.

Assume that n factors into prime numbers as both

(p₁)(p₂)(p₃) ... (p_M) = n and (q₁)(q₂)(q₃) ... (q_N) = n.

Then we have M= N and p_m = q_m for each m=1, 2, 3, ...,M. This fact is often called the Fundamental Theorem of Arithmetic. The distinct prime numbers which appear in the factorization of n are called the prime divisors of n. For example, the prime divisors of 100 are 2 and 5, and the prime divisors of 97892641 are 7, 11 and 181619. Clearly the number n is itself a prime number if its only prime divisor is n. And a number n > 1 is composite if it has a prime divisor p with 1 < p < n.

Now suppose that we want to decide if a large positive integer n is a prime. By our previous remarks it suffices to test each prime number p with 1 < p < n to see if p is a prime divisor of n. If no prime divisor p with 1 < p < n is found, then we can conclude that n itself is prime. The sieve of Eratosthenes is based on the simple observation that if n is composite then its smallest prime divisor p₁ must satisfy 1 < p₁ n. To see why this is so, assume as before that p₁, p₂, p₃,...,p_M is a collection of prime numbers arranged so that

p₁ p₂ p₃ ... p_M,

and let

(p₁)(p₂)(p₃) ... (p_M) = n

be the factorization of n as a product of prime numbers. Here p₁is the smallest prime divisor of n and therefore

(p₁)^M (p₁)(p₂)(p₃) ... (p_M) = n.

Now if n is composite then we must have 2 M. But then it follows that

p₁ n^1/M n^1/2 = n.

This shows that the smallest prime divisor p₁ of n satisfies 1 < p₁ n. Therefore, in order to determine if n is prime we only need to check for prime divisors p in the range 1 < p n.

We can turn these observations into a simple algorithm for making a list of prime numbers. Suppose that we have already determined that the prime numbers less than or equal to 10 = 100 are 2, 3, 5, and 7. Write down the integers from 2 to 100. Then cross out each integer on the list that is divisible by 2. Next cross out each integer on the list that is divisible by 3. Continue in this manner to cross out each integer on the list that is divisible by 5 and then each integer that is divisible by 7. The integers that have not been crossed out have the property that they do not have a prime divisor less than or equal to their square root. Hence the numbers that have not been crossed out are exactly the prime numbers greater than 10 and less than or equal to 100.

This is the complete article, containing 743 words (approx. 2 pages at 300 words per page).