The Sieve of Eratosthenes

Because there was a question in our first post about what a sieve is, it would be good to give a quick example of what a sieve is supposed to do, and what it looks like.

For the sake of an example, we are going to sieve all of the primes from 2-30, in other words we are going to separate the primes from the non-prime numbers in the set.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Let’s strikethrough all of the multiples of 2 greater 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 25 26 27 28 29 30

 

Now, let’s strikethrough all of the multiples of 3 greater than 3.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Now, you may be saying to me, but why didn’t you make 6, 12, 18…green too? Well, they’ve already been highlighted once in blue, so there’s no real reason to do more work than I have to.

 

So, let’s continue with 5.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

I’m going to continue going up using the non-crossed out numbers as a guide, and highlighting the multiples of those non-highlighted numbers.

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Because I only chose to go up to 30, we are actually done. The non-crossed out numbers are our prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

 

So, here are some closing thoughts about the sieve “method” of finding primes:

Pro: Easy algorithm, an easy way to loop through a set of numbers to find the primes, easy to program by hand

Con: Can take a long time with larger numbers, eats memory in larger number sets.

 

And just for a thing to brighten your day, here is a poem that I found about the sieve on Wikipedia. I take no credit because it’s not mine, but I thought it was a fun way to think about the sieve method. More information can be found at the wikipedia page on the topic, including a very cool animation of the sieve from 2-120.

 

Sift the Two’s, and Sift the Three’s,

The Sieve of Eratosthenes.

When the multiples sublime,

The numbers that remain are prime.

 

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Previous Post: Prime-Generating Functions

5 thoughts on “The Sieve of Eratosthenes

  1. Pingback: Prime-Generating Functions | MATH 287

  2. carriesmith

    I really appreciate how simple this algorithm is! I can only imagine how long it would take to use it for the larger numbers.

  3. Samuel Coskey

    Thank you for the post on this algorithm! Many people have seen it, but not everybody has seen the breakdown of its pros and cons.

    One quick comment: you seem to reference colors green and blue, but they don’t appear that way, at least not on my system.

  4. Sarah Devore Post author

    Whoops, I thought that I had changed all of the references. Originally, in the Google Doc, instead of the strikethroughs, I had a lot of pretty colors. However, when I copied it over to the post, the colors went away. It made me very sad, but I changed it to strikethroughs.

  5. Marc Garland

    A great example of using the Sieve method of finding primes! It was very easy to follow. I didn’t know the Sieve method before this post, so this was helpful for clarification.

Comments are closed.