Discrete Mathematics/Sieve of Eratosthenes

From Wikibooks, open books for an open world
Jump to: navigation, search

The Sieve of Eratosthenes is a method for find prime numbers that is attributed to the ancient Greek mathematician Eratosthenes. The idea is to begin by listing all the natural numbers bigger than 2.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 \ldots

and beginning with 2 we go to the first number that as not been crossed off and cross every multiple of that number that is later on in the list.

So in the case of 2, no numbers have been crossed so we start by removing every second number after 2. Our list would then look like

1, 2, 3, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, 9, \cancel{10}, 11, \cancel{12}, 13, \cancel{14}, 15, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, 21, \cancel{22}, 23, \cancel{24}\ldots

And we keep applying our rule. Here our next number not crossed out will be 3, we cross out every third number after 3. That will be 6, 9, 12,… and our list the becomes

1, 2, 3, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, \cancel{9}, \cancel{10}, 11, \cancel{12}, 13, \cancel{14}, \cancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, \cancel{21}, \cancel{22}, 23, \cancel{24} \ldots

And so on. At the end only the prime numbers will be left.

In this case we have already found all of the primes less than 25. This is because composite numbers must always have a prime factor less than their square root. If this were not the case for some integer n we could write n=p_1\times p_2\times\cdots\times p_k. Since we are assuming n is composite we know there are at least two prime factors p_1 and p_2. If both of which are greater than \sqrt{n}, then p_1\times p_2 > \sqrt{n}\times \sqrt{n}=n. This would contradict that n=p_1\times p_2\times\cdots\times p_k. So for us, since we have crossed out every number with a factor smaller than 5 we have crossed out every composite number less than 5^2=25.