ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

Math Series Part IX: The Sieve of Eratosthenes

Updated on November 30, 2016
Michael Ttappous profile image

Michael has been an online freelancer and writer for many years and loves discovering and sharing about new experiences and opportunities.

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.

Photo Credits:

Comments

    0 of 8192 characters used
    Post Comment

    No comments yet.