Discrete Mathematics/Sieve of Eratosthenes

Interactive SVG: Click the thumbnail, then a button to clear the table or highlight the corresponding multiples

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\dots$

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}\dots$

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}\dots$

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