Discrete Mathematics/Sieve of Eratosthenes

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 has 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$ .