Math Series Part IX: The Sieve of Eratosthenes
The Eratosthenes crible, or the sieve of Eratosthenes, is a simplistic and ancient method for determining a set of prime numbers within a given range. This is accomplished by drawing up a table of numbers and marking all—and hence eliminating—all of the numbers that are a result of a multiple of a given prime number. By doing this, we are effectively eliminating all of the composite numbers that are formed through multiplication, and therefore are left with only the prime numbers. The sieve of Eratosthenes is therefore a very useful way to find a list of smaller primes.
If we study the table below, we can immediately start by crossing out some multiples of prime factors. If we limit our range from 1 to 160 and if we use the color red to eliminate multiples of two, we get the result below; the same goes for green for multiples of 3, and blue for multiples of 5, and yellow for multiples of 7, and orange for multiples of 11. The numbers that are left unshaded are not composite numbers of any of the smaller primes, and are therefore prime numbers themselves.
It is sufficient just to use the multiples of 2, 3, 5, 7, and 11 for our range because the multiples of 13, up until 160, are all multiples of 2 or 3 or 11, and because 132 is greater than 160. However, if we were to extend our range to a larger limit, we would need to also eliminate the multiples of the succeeding prime numbers; namely that of 13, 17, 19, etc.
- Mathematical Wonders Series: Part I
In Part I of this series, we look at the fascinating Möbius band
- Mathematical Wonders Series: Part II
In Part II of this series, we look at the incredible act of doubling.
- Mathematical Wonders Series: Part III
In Part III of this series, we look at the use of Data Mining.
- Mathematical Wonders Series: Part IV
In Part IV of this series, we look at the magic of the number phi.
- Mathematical Wonders Series: Part V
In Part V of this series, we look at alternative ways to divide big numbers.
- Mathematical Wonders Series: Part VI
In Part VI of this series, we look at the 'Birthday Paradox'.
- Mathematical Wonders Series: Part VII
In Part VII of this series, we look at the beauty within Pascal's Triangle.