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.

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

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

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 we could write . Since we are assuming is composite we know there are at least two prime factors and . If both of which are greater than , then . This would contradict that . 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 .